Free CAT library

Linear Diophantine Equations & Integer Constraints

Master linear Diophantine equations ax + by = c over integer and natural number domains: Bézout's identity, modular arithmetic base extraction, parameterized stepping lattices, counting positive vs non-negative integer solutions, and the Frobenius coin theorem.

1. The Story & Mental Model: Stepping Stones Across the Integer Lattice

Imagine standing at the edge of an arithmetic river where you can only step on solid, indivisible stones. You need to settle an exact invoice of ₹293293 using only ₹77 vouchers and ₹1313 vouchers. In pure continuous geometry, the equation 7x+13y=2937x + 13y = 293 is a smooth, unbroken line slicing across the quadrant. You could pay with x=10.5x = 10.5 vouchers and y=16.88y = 16.88 vouchers. But in physical reality, vouchers, shipping crates, airline seats, and currency notes cannot be ripped into fractional shreds. You are strictly confined to the discrete universe of integers (Z\mathbb{Z}).

Only specific coordinates on that continuous line land cleanly on lattice points—intersections where both xx and yy are whole numbers.

How do you navigate from one integer lattice point to the next? Notice the fundamental conservation balance:

  • If you subtract 1313 vouchers of ₹77, you remove 13×7=₹9113 \times 7 = ₹91.

  • To restore the exact same total, you must add 77 vouchers of ₹1313, which injects 7×13=₹917 \times 13 = ₹91.

The net value does not change by a single rupee! This reveals the stepping stone invariant: along the line ax+by=cax + by = c, every time xx advances by the step size +b+b, yy must step down by −a-a. Integer solutions are not scattered randomly—they form an evenly spaced arithmetic progression marching across the coordinate plane.


2. The CAT Question Blueprint: How Exam Setters Frame Integer Constraints

Linear Diophantine equations are a crown jewel of CAT, XAT, and IPMAT quantitative aptitude because they test the bridge between algebra and number theory.

The Five Core Diophantine Exam Archetypes:

  1. The Denomination & Packaging Puzzle: A merchant buys two types of items at ₹aa and ₹bb each, spending an exact total budget of ₹cc. How many combinations of purchases are possible?

  2. The Positive vs Non-Negative Domain Trap:

    • Positive Integers: x,y∈Z+  ⟹  x≥1,y≥1x, y \in \mathbb{Z}^+ \implies x \ge 1, y \ge 1 (Zero is strictly prohibited).

    • Non-Negative Integers: x,y∈N0  ⟹  x≥0,y≥0x, y \in \mathbb{N}_0 \implies x \ge 0, y \ge 0 (Zero items of one type is permitted).

    Confusing these two phrasing variations is the single most common cause of negative marking in integer constraint problems!

  3. The Bézout Divisibility Filter: A problem presents 28x+42y=35428x + 42y = 354. Students waste precious minutes testing x=1,2,3…x = 1, 2, 3\dots, failing to realize that gcd⁡(28,42)=14\gcd(28, 42) = 14, and 1414 does not divide 354354. The answer is instantly 00 solutions!

  4. Extreme Value Optimization under Integer Budget: Given ax+by=cax + by = c, what is the maximum or minimum total number of items (x+y)(x + y) that can be acquired?

  5. The Frobenius Coin Problem (Chicken McNugget Theorem): What is the largest integer monetary amount that cannot be paid using only coins of denominations aa and bb?


3. Core Concepts, Formulae & Derivations

A. Bézout's Identity & The Existence Criterion

Theorem: For any integers a,b,ca, b, c, the linear Diophantine equation:

ax+by=cax + by = c

has at least one integer solution (x,y)∈Z2(x, y) \in \mathbb{Z}^2 if and only if the greatest common divisor of aa and bb divides cc:

gcd⁡(a,b)∣c\gcd(a, b) \mid c

Derivation / Proof:

Let g=gcd⁡(a,b)g = \gcd(a, b). By definition of a common divisor, there exist integers a′,b′a', b' such that a=g⋅a′a = g \cdot a' and b=g⋅b′b = g \cdot b'.

Substituting into the equation:

ax+by=(ga′)x+(gb′)y=g(a′x+b′y)=ca x + b y = (g a') x + (g b') y = g (a' x + b' y) = c

Since xx and yy are integers, (a′x+b′y)(a' x + b' y) must be an integer. Therefore, cc is a multiple of gg.

  • If g∤cg \nmid c, no integer solution can ever exist.

  • If g∣cg \mid c, we divide the entire equation by gg to obtain the coprime reduced form:

    a′x+b′y=c′,where gcd⁡(a′,b′)=1 and c′=cga' x + b' y = c', \quad \text{where } \gcd(a', b') = 1 \text{ and } c' = \frac{c}{g}

B. The Parameterized General Solution

Theorem: Let (x0,y0)(x_0, y_0) be any particular integer base solution to a′x+b′y=c′a' x + b' y = c', where gcd⁡(a′,b′)=1\gcd(a', b') = 1. Then the complete set of all integer solutions is parameterized by:

x=x0+b′t=x0+(bgcd⁡(a,b))tx = x_0 + b' t = x_0 + \left(\frac{b}{\gcd(a, b)}\right) t

y=y0−a′t=y0−(agcd⁡(a,b))ty = y_0 - a' t = y_0 - \left(\frac{a}{\gcd(a, b)}\right) t

for all t∈Zt \in \mathbb{Z}.

Verification:

a′x+b′y=a′(x0+b′t)+b′(y0−a′t)=(a′x0+b′y0)+(a′b′t−b′a′t)=c′+0=c′a' x + b' y = a'(x_0 + b' t) + b'(y_0 - a' t) = (a' x_0 + b' y_0) + (a' b' t - b' a' t) = c' + 0 = c'

This guarantees that every integer tt generates a valid lattice point, and Euclid's lemma proves that no other integer solutions exist.

C. The Modular Arithmetic Base Extraction Protocol

To find the initial base solution (x0,y0)(x_0, y_0) in under 15 seconds without guessing:

  1. Always isolate the variable with the smaller coefficient (say a<ba < b):

    ax+by=c  ⟹  ax=c−by  ⟹  by≡c(moda)ax + by = c \implies ax = c - by \implies by \equiv c \pmod a

  2. Reduce the coefficients bb and cc modulo aa:

    (b mod a)y≡(c mod a)(moda)(b \bmod a) y \equiv (c \bmod a) \pmod a

  3. Solve this simple one-step congruence for the smallest non-negative integer y0y_0.

  4. Substitute y0y_0 back to compute x0=c−by0ax_0 = \frac{c - b y_0}{a}.

D. Counting Positive Integer Solutions (x>0,y>0x > 0, y > 0)

Given the parameterized solution x=x0+b′tx = x_0 + b' t and y=y0−a′ty = y_0 - a' t:

Impose the positivity bounds:

x>0  ⟹  x0+b′t>0  ⟹  t>−x0b′x > 0 \implies x_0 + b' t > 0 \implies t > -\frac{x_0}{b'}

y>0  ⟹  y0−a′t>0  ⟹  t<y0a′y > 0 \implies y_0 - a' t > 0 \implies t < \frac{y_0}{a'}

The valid parameters tt form the bounded interval:

t∈(−x0b′,  y0a′)t \in \left( -\frac{x_0}{b'}, \; \frac{y_0}{a'} \right)

The number of valid solutions is simply the number of integers lying strictly inside this interval.

E. The Frobenius Coin Theorem (The McNugget Formula)

For two coprime positive integers aa and bb (with gcd⁡(a,b)=1\gcd(a, b) = 1):

  1. Largest Unobtainable Integer: The largest integer that cannot be expressed as ax+byax + by for non-negative integers x,y≥0x, y \ge 0 is:

    g(a,b)=a⋅b−a−bg(a, b) = a \cdot b - a - b

  2. Every integer strictly greater than ab−a−bab - a - b can be formed.

  3. Count of Unobtainable Integers: The total number of positive integers that cannot be formed is:

    Nunobtainable=(a−1)(b−1)2N_{\text{unobtainable}} = \frac{(a - 1)(b - 1)}{2}


4. Common Pitfalls & Speed Shortcuts

Pitfall 1: Stepping by Full Coefficients When gcd⁡(a,b)>1\gcd(a, b) > 1

If you have 6x+10y=1006x + 10y = 100, dividing by gcd⁡(6,10)=2\gcd(6, 10) = 2 gives 3x+5y=503x + 5y = 50.

  • The Error: Stepping xx by 1010 and yy by 66 skips half the solutions!
  • The Rule: Always step by the coprime reduced coefficients: xx steps by +5+5, yy steps by −3-3.

Pitfall 2: The "Zero Inclusion" Blunder

A question states: "A customer buys apples (xx) and oranges (yy)..."

  • If the question asks for different ways to buy, it implies x≥1,y≥1x \ge 1, y \ge 1 (buying 00 apples is not buying both fruits).
  • If the question specifies non-negative integers, include the boundary points where x=0x = 0 or y=0y = 0.

Pitfall 3: Brute-Force Testing Instead of Modulo Reduction

For 19x+7y=45019x + 7y = 450, testing x=1,2,3…x = 1, 2, 3\dots until 450−19x450 - 19x is divisible by 77 can take up to 7 trial divisions.

  • The Speed Shortcut: Isolate yy modulo 7:

19x≡450(mod7)  ⟹  5x≡2(mod7)19x \equiv 450 \pmod 7 \implies 5x \equiv 2 \pmod 7

Multiply by 3: 15x≡6(mod7)  ⟹  x≡6(mod7)15x \equiv 6 \pmod 7 \implies x \equiv 6 \pmod 7.

Base solution is instantly x0=6x_0 = 6! Zero trial divisions needed.

Formulas

Bézout Solvability Condition

gcd⁡(a,b)∣c\gcd(a, b) \mid c

Integer solutions exist if and only if the GCD of coefficients divides the constant
Parameterized General Diophantine Solution

x=x0+(bgcd⁡(a,b))t,y=y0−(agcd⁡(a,b))tx = x_0 + \left(\frac{b}{\gcd(a, b)}\right) t, \quad y = y_0 - \left(\frac{a}{\gcd(a, b)}\right) t

Generates all integer lattice points as parameter t traverses the integers
Frobenius Largest Unobtainable Number

g(a,b)=a⋅b−a−bg(a, b) = a \cdot b - a - b

Applies when gcd(a, b) = 1 for non-negative integers x, y >= 0
Total Unobtainable Integers Count

Nunobtainable=(a−1)(b−1)2N_{\text{unobtainable}} = \frac{(a - 1)(b - 1)}{2}

Exact count of positive integers that cannot be formed as ax + by (x, y >= 0)

Traps and tips

  • Check Bézout First: Before doing any algebra, check if gcd(a, b) divides c. If it doesn't, answer 0 solutions immediately.
  • Always Reduce by GCD: Divide ax + by = c by gcd(a, b) before stepping; step sizes are b/gcd and a/gcd.
  • Modulo the Smaller Coefficient: Isolate the variable with the smaller coefficient to find the base solution in one modular step.
  • Distinguish Positive from Non-Negative: Positive means x >= 1, y >= 1; non-negative means x >= 0, y >= 0. Don't lose marks on endpoint inclusion.

Solved examples

Example 4.1: Checking Solvability via Bézout's Identity

Determine whether the following linear equation has any integer solutions (x,y∈Z)(x, y \in \mathbb{Z}):

28x+42y=35428x + 42y = 354

Show solution

Step 1: Compute the greatest common divisor of the coefficients.

Coefficients are a=28a = 28 and b=42b = 42.

Using prime factorization:

28=22×728 = 2^2 \times 7

42=2×3×742 = 2 \times 3 \times 7

gcd⁡(28,42)=2×7=14\gcd(28, 42) = 2 \times 7 = 14

Step 2: Apply Bézout's Divisibility Criterion.

By Bézout's identity, the linear combination 28x+42y28x + 42y can only equal multiples of gcd⁡(28,42)=14\gcd(28, 42) = 14.

For integer solutions to exist, 1414 must divide the constant term 354354.

Step 3: Test divisibility of 354354 by 1414.

35414=25.2857…\frac{354}{14} = 25.2857\dots

Performing integer division:

354=14×25+4354 = 14 \times 25 + 4

The remainder is 4≠04 \ne 0. Therefore, 1414 does not divide 354354.

Conclusion:

There are zero integer solutions (x,y∈Z)(x, y \in \mathbb{Z}) that satisfy this equation.

Takeaway: Always calculate gcd(a, b) before solving; if gcd(a, b) does not divide c, conclude zero integer solutions immediately.

Example 4.2: Finding Base Solution & Parameterized Family via Modular Arithmetic

Find the complete parameterized family of integer solutions (x,y∈Z)(x, y \in \mathbb{Z}) for the linear Diophantine equation:

17x+5y=18417x + 5y = 184

Show solution

Step 1: Check gcd solvability.

gcd⁡(17,5)=1\gcd(17, 5) = 1. Since 11 divides 184184, integer solutions exist.

Step 2: Isolate the variable with the smaller coefficient modulo 5.

Since 55 is smaller than 1717, reduce the equation modulo 55:

17x+5y=184  ⟹  17x≡184(mod5)17x + 5y = 184 \implies 17x \equiv 184 \pmod 5

Reduce coefficients modulo 55:

17≡2(mod5)17 \equiv 2 \pmod 5

184=180+4≡4(mod5)184 = 180 + 4 \equiv 4 \pmod 5

Thus:

2x≡4(mod5)2x \equiv 4 \pmod 5

Step 3: Solve the modular congruence.

Divide both sides by 22 (valid since gcd⁡(2,5)=1\gcd(2, 5) = 1):

x≡2(mod5)x \equiv 2 \pmod 5

The smallest non-negative integer base value is x0=2x_0 = 2.

Step 4: Compute the corresponding y0y_0.

Substitute x0=2x_0 = 2 into the original equation:

17(2)+5y0=18417(2) + 5y_0 = 184

34+5y0=18434 + 5y_0 = 184

5y0=184−34=1505y_0 = 184 - 34 = 150

y0=1505=30y_0 = \frac{150}{5} = 30

Thus, our particular base solution is (x0,y0)=(2,30)(x_0, y_0) = (2, 30).

Step 5: Write the general parameterized solution.

Here a′=17a' = 17 and b′=5b' = 5.

x=x0+b′t=2+5tx = x_0 + b' t = 2 + 5t

y=y0−a′t=30−17ty = y_0 - a' t = 30 - 17t

for all t∈Zt \in \mathbb{Z}.

Step 6: Verification.

17(2+5t)+5(30−17t)=(34+85t)+(150−85t)=18417(2 + 5t) + 5(30 - 17t) = (34 + 85t) + (150 - 85t) = 184 (Holds for all integer tt).

Takeaway: Isolate the smaller coefficient modulo its value to extract the base solution in seconds, then step by (x 0 + bt, y 0 - at).

Example 4.3: Counting Strictly Positive Integer Solutions

A freight logistics manager must ship exactly 730 kg730\text{ kg} of industrial equipment using a combination of 13-kg13\text{-kg} crates and 19-kg19\text{-kg} crates. In how many different ways can the shipment be packed using at least one crate of each type?

Show solution

Step 1: Formulate the Diophantine model with integer constraints.

Let xx be the number of 13-kg13\text{-kg} crates and yy be the number of 19-kg19\text{-kg} crates.

13x+19y=73013x + 19y = 730

Constraints: x,y∈Z+x, y \in \mathbb{Z}^+ (strictly positive integers: x≥1,y≥1x \ge 1, y \ge 1).

Step 2: Extract base solution using modular arithmetic.

Modulo 1313 (the smaller coefficient):

13x+19y=730  ⟹  19y≡730(mod13)13x + 19y = 730 \implies 19y \equiv 730 \pmod{13}

19≡6(mod13)19 \equiv 6 \pmod{13}

730=13×56+2  ⟹  730≡2(mod13)730 = 13 \times 56 + 2 \implies 730 \equiv 2 \pmod{13}

6y≡2(mod13)6y \equiv 2 \pmod{13}

Multiply both sides by 22:

12y≡4(mod13)12y \equiv 4 \pmod{13}

Since 12≡−1(mod13)12 \equiv -1 \pmod{13}:

−y≡4(mod13)  ⟹  y≡−4≡9(mod13)-y \equiv 4 \pmod{13} \implies y \equiv -4 \equiv 9 \pmod{13}

Thus, the base solution for yy is y0=9y_0 = 9.

Step 3: Compute x0x_0.

13x0+19(9)=73013x_0 + 19(9) = 730

13x0+171=73013x_0 + 171 = 730

13x0=559  ⟹  x0=55913=4313x_0 = 559 \implies x_0 = \frac{559}{13} = 43

Base solution: (x0,y0)=(43,9)(x_0, y_0) = (43, 9).

Step 4: Parameterize all integer solutions.

x=43−19tx = 43 - 19t

y=9+13ty = 9 + 13t

Step 5: Apply positivity conditions (x≥1,y≥1x \ge 1, y \ge 1).

  1. For x≥1x \ge 1:

    43−19t≥1  ⟹  19t≤42  ⟹  t≤4219≈2.2143 - 19t \ge 1 \implies 19t \le 42 \implies t \le \frac{42}{19} \approx 2.21

  2. For y≥1y \ge 1:

    9+13t≥1  ⟹  13t≥−8  ⟹  t≥−813≈−0.619 + 13t \ge 1 \implies 13t \ge -8 \implies t \ge -\frac{8}{13} \approx -0.61

Step 6: Count integer values of tt.

−0.61≤t≤2.21  ⟹  t∈{0,1,2}-0.61 \le t \le 2.21 \implies t \in \{0, 1, 2\}

There are exactly 3 solutions:

  • t=0  ⟹  (x,y)=(43,9)t = 0 \implies (x, y) = (43, 9)

  • t=1  ⟹  (x,y)=(24,22)t = 1 \implies (x, y) = (24, 22)

  • t=2  ⟹  (x,y)=(5,35)t = 2 \implies (x, y) = (5, 35)

The shipment can be configured in exactly 33 different ways.

Takeaway: Strictly positive solutions require x = 1 and y = 1; solve for integer bounds on parameter t to count solutions directly.

Example 4.4: Maximizing & Minimizing Total Items under Budget Constraint

An event coordinator spends exactly ₹293293 on decorative banners. Standard banners cost ₹77 each and Premium banners cost ₹1313 each. If at least one banner of each type must be purchased, find:

(a) The maximum total number of banners that can be bought.

(b) The minimum total number of banners that can be bought.

Show solution

Step 1: Set up the Diophantine model.

Let xx be the number of Standard banners (₹77) and yy be the number of Premium banners (₹1313).

7x+13y=293,x,y∈Z+7x + 13y = 293, \quad x, y \in \mathbb{Z}^+

Total banners: N=x+yN = x + y.

Step 2: Find the base solution modulo 7.

13y≡293(mod7)13y \equiv 293 \pmod 7

13≡6≡−1(mod7)13 \equiv 6 \equiv -1 \pmod 7

293=7×41+6≡6≡−1(mod7)293 = 7 \times 41 + 6 \equiv 6 \equiv -1 \pmod 7

−y≡−1(mod7)  ⟹  y≡1(mod7)-y \equiv -1 \pmod 7 \implies y \equiv 1 \pmod 7

Base value: y0=1y_0 = 1.

Compute x0x_0:

7x0+13(1)=293  ⟹  7x0=280  ⟹  x0=407x_0 + 13(1) = 293 \implies 7x_0 = 280 \implies x_0 = 40

Base solution: (x0,y0)=(40,1)(x_0, y_0) = (40, 1).

Step 3: Parameterize the solutions.

x=40−13tx = 40 - 13t

y=1+7ty = 1 + 7t

Step 4: Find the valid range of tt for x≥1,y≥1x \ge 1, y \ge 1.

  • x≥1  ⟹  40−13t≥1  ⟹  13t≤39  ⟹  t≤3x \ge 1 \implies 40 - 13t \ge 1 \implies 13t \le 39 \implies t \le 3

  • y≥1  ⟹  1+7t≥1  ⟹  7t≥0  ⟹  t≥0y \ge 1 \implies 1 + 7t \ge 1 \implies 7t \ge 0 \implies t \ge 0

Thus, t∈{0,1,2,3}t \in \{0, 1, 2, 3\}.

Step 5: Formulate the total banner objective N(t)=x+yN(t) = x + y.

N(t)=(40−13t)+(1+7t)=41−6tN(t) = (40 - 13t) + (1 + 7t) = 41 - 6t

Notice that N(t)N(t) decreases by 66 for each step increase in tt because cheaper ₹77 banners are being replaced by more expensive ₹1313 banners!

Step 6: Compute the extreme values.

  • Maximum Banners (t=0t = 0):

    x=40,  y=1  ⟹  Nmax⁡=40+1=41x = 40, \; y = 1 \implies N_{\max} = 40 + 1 = 41

  • Minimum Banners (t=3t = 3):

    x=40−13(3)=1,  y=1+7(3)=22  ⟹  Nmin⁡=1+22=23x = 40 - 13(3) = 1, \; y = 1 + 7(3) = 22 \implies N_{\min} = 1 + 22 = 23

Maximum banners =41= 41; Minimum banners =23= 23.

Takeaway: Total quantity x + y changes by (b - a) at each parameter step; maximize total items by maximizing the cheaper item.

Example 4.5: Non-Negative vs Strictly Positive Integer Solution Comparison

Consider the linear Diophantine equation:

7x+11y=3417x + 11y = 341

Determine:

(a) The number of non-negative integer solutions (x,y≥0x, y \ge 0).

(b) The number of strictly positive integer solutions (x,y≥1x, y \ge 1).

Show solution

Step 1: Check solvability and find a base solution.

gcd⁡(7,11)=1\gcd(7, 11) = 1. Since 341=11×31341 = 11 \times 31, notice that if x=0x = 0:

7(0)+11(31)=3417(0) + 11(31) = 341

Thus, (x0,y0)=(0,31)(x_0, y_0) = (0, 31) is an immediate exact base solution!

Step 2: Parameterize all integer solutions.

x=0+11t=11tx = 0 + 11t = 11t

y=31−7ty = 31 - 7t

Step 3: Part (a) - Non-negative integer solutions (x≥0,y≥0x \ge 0, y \ge 0).

  • x≥0  ⟹  11t≥0  ⟹  t≥0x \ge 0 \implies 11t \ge 0 \implies t \ge 0

  • y≥0  ⟹  31−7t≥0  ⟹  7t≤31  ⟹  t≤317≈4.428y \ge 0 \implies 31 - 7t \ge 0 \implies 7t \le 31 \implies t \le \frac{31}{7} \approx 4.428

Valid integer values for tt:

t∈{0,1,2,3,4}t \in \{0, 1, 2, 3, 4\}

There are 5 non-negative integer solutions:

  • t=0  ⟹  (0,31)t = 0 \implies (0, 31)

  • t=1  ⟹  (11,24)t = 1 \implies (11, 24)

  • t=2  ⟹  (22,17)t = 2 \implies (22, 17)

  • t=3  ⟹  (33,10)t = 3 \implies (33, 10)

  • t=4  ⟹  (44,3)t = 4 \implies (44, 3)

Step 4: Part (b) - Strictly positive integer solutions (x≥1,y≥1x \ge 1, y \ge 1).

  • x≥1  ⟹  11t≥1  ⟹  t≥111  ⟹  t≥1x \ge 1 \implies 11t \ge 1 \implies t \ge \frac{1}{11} \implies t \ge 1 (excludes t=0t = 0 where x=0x = 0)

  • y≥1  ⟹  31−7t≥1  ⟹  7t≤30  ⟹  t≤307≈4.28y \ge 1 \implies 31 - 7t \ge 1 \implies 7t \le 30 \implies t \le \frac{30}{7} \approx 4.28

Valid integer values for tt:

t∈{1,2,3,4}t \in \{1, 2, 3, 4\}

There are 4 strictly positive integer solutions.

Non-negative count =5= 5; Positive count =4= 4.

Takeaway: Zero inclusion makes all the difference: non-negative domains include boundary points (x = 0 or y = 0), while positive domains strictly exclude them.

Example 4.6: The Frobenius Coin Problem (Largest Unobtainable Amount)

An ancient postal system issues stamps exclusively in two denominations: 7 cents7\text{ cents} and 11 cents11\text{ cents}.

(a) Find the largest postage amount that cannot be formed using any combination of these stamps.

(b) Prove that every integer postage amount greater than or equal to 60 cents60\text{ cents} can be formed.

Show solution

Step 1: Check conditions and apply Frobenius Formula.

The denominations are a=7a = 7 and b=11b = 11.

Since gcd⁡(7,11)=1\gcd(7, 11) = 1, the Frobenius Coin Formula applies for non-negative integers x,y≥0x, y \ge 0:

g(a,b)=a⋅b−a−bg(a, b) = a \cdot b - a - b

g(7,11)=7×11−7−11=77−18=59 centsg(7, 11) = 7 \times 11 - 7 - 11 = 77 - 18 = 59\text{ cents}

Thus, the largest impossible postage amount is 59 cents.

Step 2: Prove that 59 cannot be formed.

Assume for contradiction that 7x+11y=597x + 11y = 59 for integers x,y≥0x, y \ge 0.

Test possible non-negative values of yy:

  • If y=0  ⟹  7x=59y = 0 \implies 7x = 59 (59 is not divisible by 7)

  • If y=1  ⟹  7x=59−11=48y = 1 \implies 7x = 59 - 11 = 48 (48 is not divisible by 7)

  • If y=2  ⟹  7x=59−22=37y = 2 \implies 7x = 59 - 22 = 37 (37 is not divisible by 7)

  • If y=3  ⟹  7x=59−33=26y = 3 \implies 7x = 59 - 33 = 26 (26 is not divisible by 7)

  • If y=4  ⟹  7x=59−44=15y = 4 \implies 7x = 59 - 44 = 15 (15 is not divisible by 7)

  • If y=5  ⟹  7x=59−55=4y = 5 \implies 7x = 59 - 55 = 4 (4 is not divisible by 7)

  • If y≥6  ⟹  11y≥66>59y \ge 6 \implies 11y \ge 66 > 59 (Impossible since x≥0x \ge 0)

Hence, 5959 cannot be formed.

Step 3: Prove that all integers ≥60\ge 60 can be formed.

By mathematical induction, if 77 consecutive integers can be formed, then every subsequent integer can be obtained by repeatedly adding 7-cent7\text{-cent} stamps (+7k+7k).

We construct representations for the 77 consecutive integers from 6060 to 6666:

  • 60=7(7)+11(1)=49+11=6060 = 7(7) + 11(1) = 49 + 11 = 60

  • 61=7(4)+11(3)=28+33=6161 = 7(4) + 11(3) = 28 + 33 = 61

  • 62=7(1)+11(5)=7+55=6262 = 7(1) + 11(5) = 7 + 55 = 62

  • 63=7(9)+11(0)=63+0=6363 = 7(9) + 11(0) = 63 + 0 = 63

  • 64=7(6)+11(2)=42+22=6464 = 7(6) + 11(2) = 42 + 22 = 64

  • 65=7(3)+11(4)=21+44=6565 = 7(3) + 11(4) = 21 + 44 = 65

  • 66=7(0)+11(6)=0+66=6666 = 7(0) + 11(6) = 0 + 66 = 66

Since 77 consecutive integers {60,61,62,63,64,65,66}\{60, 61, 62, 63, 64, 65, 66\} are successfully represented, adding multiples of 77 to these base solutions generates all integers ≥60\ge 60.

Largest unobtainable postage is 59 cents59\text{ cents}.

Takeaway: For coprime denominations a and b, the Frobenius formula g(a,b) = ab - a - b gives the exact largest impossible integer.

Practice questions

Question 1 · CAT Level

How many pairs of positive integers (x,y)(x, y) satisfy the linear Diophantine equation 7x+11y=2507x + 11y = 250?

  1. A

    22

  2. B

    33

  3. C

    44

  4. D

    55

Show answer and explanation

Answer: (B) 3

Take modulo 77: 11y≡250(mod7)  ⟹  4y≡5(mod7)11y \equiv 250 \pmod{7} \implies 4y \equiv 5 \pmod{7}.

Multiplying by 22: 8y≡10  ⟹  y≡3(mod7)8y \equiv 10 \implies y \equiv 3 \pmod{7}.

The smallest positive value is y=3y = 3: 7x=250−33=217  ⟹  x=317x = 250 - 33 = 217 \implies x = 31.

The general integer solution is x=31−11tx = 31 - 11t and y=3+7ty = 3 + 7t for integer tt.

For x>0x > 0: 31−11t≥1  ⟹  11t≤30  ⟹  t≤231 - 11t \ge 1 \implies 11t \le 30 \implies t \le 2. For y>0y > 0: t≥0t \ge 0.

Thus t∈{0,1,2}t \in \{0, 1, 2\}, yielding exactly 33 positive integer pairs.

Question 2 · CAT Level

How many pairs of non-negative integers (x,y)(x, y) satisfy 5x+9y=1805x + 9y = 180?

  1. A

    44

  2. B

    55

  3. C

    66

  4. D

    77

Show answer and explanation

Answer: (B) 5

Take modulo 55: 9y≡180(mod5)  ⟹  4y≡0(mod5)  ⟹  y9y \equiv 180 \pmod{5} \implies 4y \equiv 0 \pmod{5} \implies y must be a multiple of 55.

Let y=5ky = 5k for non-negative integer kk: 5x+9(5k)=180  ⟹  x+9k=36  ⟹  x=36−9k5x + 9(5k) = 180 \implies x + 9k = 36 \implies x = 36 - 9k.

For non-negative solutions, x≥0  ⟹  36−9k≥0  ⟹  9k≤36  ⟹  k≤4x \ge 0 \implies 36 - 9k \ge 0 \implies 9k \le 36 \implies k \le 4.

Since k≥0k \ge 0, the allowable values are k∈{0,1,2,3,4}k \in \{0, 1, 2, 3, 4\}.

This gives exactly 55 non-negative integer pairs.

Question 3 · CAT Level

A cashier has an exact sum of ₹175175 made up entirely of ₹22 and ₹55 coins. If there are at least 55 coins of each denomination, how many distinct combinations of coins are possible?

  1. A

    1313

  2. B

    1414

  3. C

    1515

  4. D

    1616

Show answer and explanation

Answer: (C) 15

The Diophantine equation is 2x+5y=1752x + 5y = 175 with x≥5,y≥5x \ge 5, y \ge 5.

Taking modulo 22: 5y≡175≡1(mod2)  ⟹  y5y \equiv 175 \equiv 1 \pmod{2} \implies y must be odd.

Smallest valid y≥5y \ge 5 is y=5y = 5: 2x=175−25=150  ⟹  x=75≥52x = 175 - 25 = 150 \implies x = 75 \ge 5.

Largest valid yy: 2(5)+5y≤175  ⟹  5y≤165  ⟹  y≤332(5) + 5y \le 175 \implies 5y \le 165 \implies y \le 33.

Allowable odd values: y∈{5,7,9,…,33}y \in \{5, 7, 9, \dots, 33\}.

Number of terms =33−52+1=14+1=15= \frac{33 - 5}{2} + 1 = 14 + 1 = 15 combinations.

Question 4 · CAT Level

For how many integer values of cc in the range 1≤c≤1001 \le c \le 100 does the linear equation 14x+21y=c14x + 21y = c possess integer solutions?

  1. A

    1212

  2. B

    1414

  3. C

    1616

  4. D

    2121

Show answer and explanation

Answer: (B) 14

By Bézout's Identity, ax+by=cax + by = c has integer solutions if and only if gcd⁡(a,b)\gcd(a, b) divides cc.

Here gcd⁡(14,21)=7\gcd(14, 21) = 7.

Thus, the equation is solvable if and only if cc is a multiple of 77.

In the range 1≤c≤1001 \le c \le 100, the number of multiples of 77 is ⌊100/7⌋=14\lfloor 100/7 \rfloor = 14.

Question 5 · CAT Level

What is the minimum possible value of x+yx + y for positive integers (x,y)(x, y) satisfying 13x+19y=50013x + 19y = 500?

  1. A

    3030

  2. B

    3232

  3. C

    3535

  4. D

    3838

Show answer and explanation

Answer: (B) 32

Take modulo 1313: 19y≡500(mod13)  ⟹  6y≡6(mod13)  ⟹  y≡1(mod13)19y \equiv 500 \pmod{13} \implies 6y \equiv 6 \pmod{13} \implies y \equiv 1 \pmod{13}.

For y=1y = 1: 13x=500−19=481  ⟹  x=3713x = 500 - 19 = 481 \implies x = 37. Here x+y=37+1=38x + y = 37 + 1 = 38.

For y=1+13=14y = 1 + 13 = 14: 13x=500−19(14)=500−266=234  ⟹  x=1813x = 500 - 19(14) = 500 - 266 = 234 \implies x = 18. Here x+y=18+14=32x + y = 18 + 14 = 32.

For y=14+13=27y = 14 + 13 = 27: 19(27)=513>50019(27) = 513 > 500, which gives no positive xx.

The minimum value of x+yx + y is 3232.

Try real CAT questions

Study this concept with interactive practice in PrepSoc.

Open the concept library