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 ₹ using only ₹ vouchers and ₹ vouchers. In pure continuous geometry, the equation is a smooth, unbroken line slicing across the quadrant. You could pay with vouchers and 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 ().
Only specific coordinates on that continuous line land cleanly on lattice points—intersections where both and are whole numbers.
How do you navigate from one integer lattice point to the next? Notice the fundamental conservation balance:
-
If you subtract vouchers of ₹, you remove .
-
To restore the exact same total, you must add vouchers of ₹, which injects .
The net value does not change by a single rupee! This reveals the stepping stone invariant: along the line , every time advances by the step size , must step down by . 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:
-
The Denomination & Packaging Puzzle: A merchant buys two types of items at ₹ and ₹ each, spending an exact total budget of ₹. How many combinations of purchases are possible?
-
The Positive vs Non-Negative Domain Trap:
-
Positive Integers: (Zero is strictly prohibited).
-
Non-Negative Integers: (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!
-
-
The Bézout Divisibility Filter: A problem presents . Students waste precious minutes testing , failing to realize that , and does not divide . The answer is instantly solutions!
-
Extreme Value Optimization under Integer Budget: Given , what is the maximum or minimum total number of items that can be acquired?
-
The Frobenius Coin Problem (Chicken McNugget Theorem): What is the largest integer monetary amount that cannot be paid using only coins of denominations and ?
3. Core Concepts, Formulae & Derivations
A. Bézout's Identity & The Existence Criterion
Theorem: For any integers , the linear Diophantine equation:
has at least one integer solution if and only if the greatest common divisor of and divides :
Derivation / Proof:
Let . By definition of a common divisor, there exist integers such that and .
Substituting into the equation:
Since and are integers, must be an integer. Therefore, is a multiple of .
-
If , no integer solution can ever exist.
-
If , we divide the entire equation by to obtain the coprime reduced form:
B. The Parameterized General Solution
Theorem: Let be any particular integer base solution to , where . Then the complete set of all integer solutions is parameterized by:
for all .
Verification:
This guarantees that every integer 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 in under 15 seconds without guessing:
-
Always isolate the variable with the smaller coefficient (say ):
-
Reduce the coefficients and modulo :
-
Solve this simple one-step congruence for the smallest non-negative integer .
-
Substitute back to compute .
D. Counting Positive Integer Solutions ()
Given the parameterized solution and :
Impose the positivity bounds:
The valid parameters form the bounded interval:
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 and (with ):
-
Largest Unobtainable Integer: The largest integer that cannot be expressed as for non-negative integers is:
-
Every integer strictly greater than can be formed.
-
Count of Unobtainable Integers: The total number of positive integers that cannot be formed is:
4. Common Pitfalls & Speed Shortcuts
Pitfall 1: Stepping by Full Coefficients When
If you have , dividing by gives .
- The Error: Stepping by and by skips half the solutions!
- The Rule: Always step by the coprime reduced coefficients: steps by , steps by .
Pitfall 2: The "Zero Inclusion" Blunder
A question states: "A customer buys apples () and oranges ()..."
- If the question asks for different ways to buy, it implies (buying apples is not buying both fruits).
- If the question specifies non-negative integers, include the boundary points where or .
Pitfall 3: Brute-Force Testing Instead of Modulo Reduction
For , testing until is divisible by can take up to 7 trial divisions.
- The Speed Shortcut: Isolate modulo 7:
Multiply by 3: .
Base solution is instantly ! Zero trial divisions needed.
Formulas
| Bézout Solvability Condition | |
|---|---|
| Parameterized General Diophantine Solution | |
| Frobenius Largest Unobtainable Number | |
| Total Unobtainable Integers Count |
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 :
Show solution
Step 1: Compute the greatest common divisor of the coefficients.
Coefficients are and .
Using prime factorization:
Step 2: Apply Bézout's Divisibility Criterion.
By Bézout's identity, the linear combination can only equal multiples of .
For integer solutions to exist, must divide the constant term .
Step 3: Test divisibility of by .
Performing integer division:
The remainder is . Therefore, does not divide .
Conclusion:
There are zero integer solutions 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 for the linear Diophantine equation:
Show solution
Step 1: Check gcd solvability.
. Since divides , integer solutions exist.
Step 2: Isolate the variable with the smaller coefficient modulo 5.
Since is smaller than , reduce the equation modulo :
Reduce coefficients modulo :
Thus:
Step 3: Solve the modular congruence.
Divide both sides by (valid since ):
The smallest non-negative integer base value is .
Step 4: Compute the corresponding .
Substitute into the original equation:
Thus, our particular base solution is .
Step 5: Write the general parameterized solution.
Here and .
for all .
Step 6: Verification.
(Holds for all integer ).
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 of industrial equipment using a combination of crates and 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 be the number of crates and be the number of crates.
Constraints: (strictly positive integers: ).
Step 2: Extract base solution using modular arithmetic.
Modulo (the smaller coefficient):
Multiply both sides by :
Since :
Thus, the base solution for is .
Step 3: Compute .
Base solution: .
Step 4: Parameterize all integer solutions.
Step 5: Apply positivity conditions ().
-
For :
-
For :
Step 6: Count integer values of .
There are exactly 3 solutions:
The shipment can be configured in exactly 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 ₹ on decorative banners. Standard banners cost ₹ each and Premium banners cost ₹ 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 be the number of Standard banners (₹) and be the number of Premium banners (₹).
Total banners: .
Step 2: Find the base solution modulo 7.
Base value: .
Compute :
Base solution: .
Step 3: Parameterize the solutions.
Step 4: Find the valid range of for .
Thus, .
Step 5: Formulate the total banner objective .
Notice that decreases by for each step increase in because cheaper ₹ banners are being replaced by more expensive ₹ banners!
Step 6: Compute the extreme values.
-
Maximum Banners ():
-
Minimum Banners ():
Maximum banners ; Minimum banners .
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:
Determine:
(a) The number of non-negative integer solutions ().
(b) The number of strictly positive integer solutions ().
Show solution
Step 1: Check solvability and find a base solution.
. Since , notice that if :
Thus, is an immediate exact base solution!
Step 2: Parameterize all integer solutions.
Step 3: Part (a) - Non-negative integer solutions ().
Valid integer values for :
There are 5 non-negative integer solutions:
Step 4: Part (b) - Strictly positive integer solutions ().
-
(excludes where )
-
Valid integer values for :
There are 4 strictly positive integer solutions.
Non-negative count ; Positive count .
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: and .
(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 can be formed.
Show solution
Step 1: Check conditions and apply Frobenius Formula.
The denominations are and .
Since , the Frobenius Coin Formula applies for non-negative integers :
Thus, the largest impossible postage amount is 59 cents.
Step 2: Prove that 59 cannot be formed.
Assume for contradiction that for integers .
Test possible non-negative values of :
-
If (59 is not divisible by 7)
-
If (48 is not divisible by 7)
-
If (37 is not divisible by 7)
-
If (26 is not divisible by 7)
-
If (15 is not divisible by 7)
-
If (4 is not divisible by 7)
-
If (Impossible since )
Hence, cannot be formed.
Step 3: Prove that all integers can be formed.
By mathematical induction, if consecutive integers can be formed, then every subsequent integer can be obtained by repeatedly adding stamps ().
We construct representations for the consecutive integers from to :
Since consecutive integers are successfully represented, adding multiples of to these base solutions generates all integers .
Largest unobtainable postage is .
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 satisfy the linear Diophantine equation ?
Show answer and explanation
Answer: (B) 3
Take modulo : .
Multiplying by : .
The smallest positive value is : .
The general integer solution is and for integer .
For : . For : .
Thus , yielding exactly positive integer pairs.
Question 2 · CAT Level
How many pairs of non-negative integers satisfy ?
Show answer and explanation
Answer: (B) 5
Take modulo : must be a multiple of .
Let for non-negative integer : .
For non-negative solutions, .
Since , the allowable values are .
This gives exactly non-negative integer pairs.
Question 3 · CAT Level
A cashier has an exact sum of ₹ made up entirely of ₹ and ₹ coins. If there are at least coins of each denomination, how many distinct combinations of coins are possible?
Show answer and explanation
Answer: (C) 15
The Diophantine equation is with .
Taking modulo : must be odd.
Smallest valid is : .
Largest valid : .
Allowable odd values: .
Number of terms combinations.
Question 4 · CAT Level
For how many integer values of in the range does the linear equation possess integer solutions?
Show answer and explanation
Answer: (B) 14
By Bézout's Identity, has integer solutions if and only if divides .
Here .
Thus, the equation is solvable if and only if is a multiple of .
In the range , the number of multiples of is .
Question 5 · CAT Level
What is the minimum possible value of for positive integers satisfying ?
Show answer and explanation
Answer: (B) 32
Take modulo : .
For : . Here .
For : . Here .
For : , which gives no positive .
The minimum value of is .
Try real CAT questions
Study this concept with interactive practice in PrepSoc.
Open the concept library