Integer equations and modular methods

Whole tables, rather than fractions of tables

A room needs exactly 18 seats. You can use four-seat tables and six-seat tables. Let x count the four-seat tables and y the six-seat tables. Then 4x+6y=18, with x and y nonnegative integers. Three six-seat tables work: (x,y)=(0,3). Three four-seat tables and one six-seat table also work: (3,1).

Solving the equation over real numbers gives a whole straight line, including fractional table counts. The integer solutions are only the grid points on that line. The nonnegative requirement selects fewer points again. State the equation and the permitted values together; they answer different parts of the problem.

Useful preparation is whole-number multiplication and division, negative numbers, reversible equation steps, plotting coordinate pairs, and inequality bounds. The linked published lessons supply those skills. Divisibility, greatest common divisors, Bézout’s identity and congruence notation are explained here, so you need not have read another number-theory lesson first.

On a first reading, follow the table problem, the divisibility test and the one-parameter family, then filter it to nonnegative counts. Return to the proof that the family is complete and the congruence-class count after trying the worked examples. The nonlinear section uses only the modular rules introduced here.

First check whether the target is reachable at all

An integer is one of …,−2,−1,0,1,2,…; write their set as ℤ. An equation with specified integer unknowns is called a Diophantine equation. In ax+by=c, the given coefficients a,b and target c are also integers. A negative unknown is allowed unless an additional condition excludes it.

For integers d and n, d | n means n=dk for some integer k. Thus 3 divides both 6 and 9, and it divides every integer combination 6x+9y=3(2x+3y). The equation 6x+9y=5 has no integer solution, since 5 is not divisible by 3. Finding no point in a small drawing would not establish this global impossibility.

If a,b are not both zero, g=gcd(a,b) is their greatest positive common divisor. Signs do not affect the positive common divisors; gcd(−6,9)=3 and gcd(a,0)=|a| for a≠0. Both-zero inputs have every positive integer as a common divisor and no greatest one; when needed, use the convention gcd(0,0)=0.

Because g divides a and b, any solution must satisfy g | c. This is the necessary condition. For coefficients not both zero it is also sufficient, but that direction needs an actual integer construction, supplied next. The gcd is positive in that theorem; never divide by the both-zero convention.

An integer combination of the coefficients supplies a starting point

Bézout’s identity states that, for a,b not both zero, there are integers u,v with au+bv=gcd(a,b). Here is why it holds. Start from |a| and |b|. When B>0, divide A=qB+r with 0≤r<B, and replace (A,B) by (B,r). A divisor of A and B divides r=A−qB; conversely a divisor of B and r divides A=qB+r. Thus the common-divisor set is unchanged.

The positive second entries strictly decrease, so the process stops at (g,0). Since the terminal gcd is its first entry, this is the original positive gcd. Each initial absolute value is an integer combination of the original signed inputs: |a|=a×sgn(a) and |b|=b×sgn(b), where sgn is 1,−1 or 0 according to the sign. Subtracting q times one combination from the other keeps integer coefficients. Hence the terminal g is au+bv, proving the identity, including a single zero input.

If c=gk for an integer k, multiply au+bv=g by k. Then x₀=uk and y₀=vk give ax₀+by₀=c. Combined with the necessary condition, this proves: for a,b not both zero, integer solutions exist exactly when gcd(a,b) divides c. A particular solution means one such starting pair; it need not meet later nonnegative restrictions.

For 4 and 6, the remainder 6−4=2 gives g=2 and 4×(−1)+6×1=2. Multiply by 18/2=9 to obtain (x₀,y₀)=(−9,9). It is a valid integer solution of 4x+6y=18, even though a negative number of tables would be unusable. Moving through the full family will find the usable pairs.

One integer step gives all solutions

Suppose a,b are not both zero and g | c. From any particular solution (x₀,y₀), every integer t gives x=x₀+(b/g)t and y=y₀−(a/g)t. Substituting cancels the two added terms: a(b/g)t−b(a/g)t=0. So every listed pair is a solution. The parameter t must be an integer; real t would fill the real line instead.

For 4x+6y=18, use (−9,9) and the step (3,−2). Then x=−9+3t and y=9−2t, t∈ℤ. Each move adds three four-seat tables and removes two six-seat tables, preserving 12 seats added and 12 removed. The lattice diagram shows only a bounded portion of this infinite family.

Why are no integer solutions omitted? Write α=a/g and β=b/g. They are coprime: a positive common divisor h>1 would make gh a common divisor of a,b larger than g. If gcd(α,β)=1 and β | αk, Bézout gives αs+βr=1; multiply by k to see β divides k. This cancellation uses integer divisibility, rather than division of real numbers.

Subtract a particular solution from any other solution to get α(x−x₀)+β(y−y₀)=0. If b≠0, β divides α(x−x₀), so cancellation gives x−x₀=βt for an integer t. Substitute back and divide by nonzero β to obtain y−y₀=−αt. Thus the family contains every solution. If b=0 and a≠0, x is fixed while y is arbitrary; because a/g is 1 or −1, the same formula covers every integer y.

One convenient starting pair for −2x+3y=1 is (1,1). With g=1, the complete family is (x,y)=(1+3t,1+2t), t∈ℤ. Signed coefficients change the direction of the step; the proof and the positivity of g remain the same. Different particular solutions merely shift the parameter’s origin.

A free unknown and an all-plane equation are different cases

If a=0 and b≠0, the equation is by=c. It is solvable exactly when b divides c; then y=c/b and x is any integer. If b=0 and a≠0, x=c/a is fixed when integral and y is any integer. For example, −3y=6 gives y=−2 and every integer x; adding a nonnegative condition on y would make the count problem impossible.

If a=b=0 and c=0, the equation is 0=0. Every pair (x,y)∈ℤ² works, with two independent integer choices. A single line family cannot describe this whole plane. If a=b=0 and c≠0, there are no solutions. Treat both-zero cases directly instead of dividing by gcd 0.

Do not infer that a zero coefficient makes the corresponding unknown zero. It makes that unknown absent from the equation and therefore free, subject only to any additional domain restrictions. Likewise, infinitely many integer solutions need not mean infinitely many nonnegative solutions.

Translate the count restrictions into integer parameter bounds

Return to x=−9+3t and y=9−2t. The table counts require −9+3t≥0, giving t≥3, and 9−2t≥0, giving t≤9/2. Since t is an integer, t≤4. Thus t=3 or 4, giving precisely (0,3) and (3,1). This proves completeness of the usable solutions, rather than just finding two examples.

In general, a coordinate h+kt≥0 gives t≥ceil(−h/k) if k>0, and t≤floor(−h/k) if k<0. Here ceil(s) is the least integer at least s, and floor(s) the greatest integer at most s. Division by a negative number reverses the inequality. If k=0, the coordinate is constant: h≥0 imposes no bound, while h<0 excludes every parameter.

Combine all lower bounds by taking the largest and all upper bounds by taking the smallest. If the resulting lower bound exceeds the upper bound, no integer t survives. A missing bound means that direction is unbounded; it is not replaced by an arbitrary drawing limit. For 4x+6y=2, the family x=−1+3t,y=1−2t requires t≥1 and t≤0, so there is no nonnegative solution despite integer solvability.

For −2x+3y=1, the convenient family (1+3t,1+2t) is nonnegative exactly when t≥0. There are infinitely many such pairs. With positive coefficients and positive target, both counts are bounded above; with mixed coefficient signs they need not be. The finite displayed window is separate from the actual parameter bounds.

A remainder condition hides one integer unknown

For a positive integer modulus m, write z≡w (mod m) when m | z−w. The normalized residues are 0,1,…,m−1. Every signed integer has a unique such residue: choose q=floor(z/m) and r=z−qm to get 0≤r<m. Two integers have the same residue exactly when their difference is a multiple of m. For example, −3≡4 (mod 7).

The congruence ax≡c (mod m) means ax−c is a multiple of m. Equivalently there exists an integer y with ax+my=c: if ax−c=mk, choose y=−k, and the reverse implication follows by rearranging. Therefore the positive gcd g=gcd(a,m) divides c exactly when the congruence is solvable. The modulus m≥1 guarantees that the coefficients are not both zero.

One solution x₀ comes from Bézout for (a,m), multiplied by c/g. The complete integer equation family shows that all congruence solutions are x=x₀+(m/g)t, t∈ℤ. The y coordinate is unnecessary once its existence is established. This describes all integers, rather than only a short residue table.

Modulo m there are exactly g distinct solution classes, represented by x₀+j(m/g) for j=0,…,g−1, then normalized into 0,…,m−1. Two of these could agree modulo m only if g divides their index difference, which is strictly between −g and g; hence the indices must agree. Every integer t has a remainder j modulo g, proving the list is complete. For m=1 there is one residue, 0, and every integer solves every linear congruence modulo 1.

Cancel a common factor only with the correct modulus

Solve 6x≡4 (mod 10). The gcd is 2, which divides 4. Writing 6x−4=10k and dividing the whole equality by 2 gives 3x−2=5k. Thus the equivalent congruence is 3x≡2 (mod 5), with the reduced modulus 5. Since 3×2≡1 (mod 5), multiplying by 2 gives x≡4 (mod 5).

All integers are x=4+5t. The two classes modulo 10 are 4 and 9, agreeing with g=2. Keeping modulus 10 after cancelling to 3x≡2 would discard valid solutions; for example x=9 solves the original, but 27 is not congruent to 2 modulo 10.

More generally, if g | c, division gives (a/g)x≡c/g (mod m/g). The reduced coefficient is coprime to the reduced modulus. Bézout supplies an integer u with (a/g)u≡1 (mod m/g), so x≡u(c/g) modulo the reduced modulus. If m/g=1, the congruence imposes no restriction on integers; there is no need to invoke a special inverse convention.

Do not cancel an arbitrary noninvertible factor while retaining the modulus. From 2x≡0 (mod 6), the correct conclusion is x≡0 (mod 3), not x≡0 (mod 6). The original solutions include x=3. The existence test also distinguishes 6x≡3 (mod 10): its gcd 2 does not divide 3, so no class works.

An impossible residue proves an impossible integer equation

Congruence respects sums and products. If z=r+mk and w=s+mℓ, then z+w−(r+s)=m(k+ℓ), and zw−rs=m(rℓ+sk+mkℓ). Both differences are divisible by m. In particular, squaring a residue gives the residue of the square. These rules let finite remainder cases constrain every integer, including negative ones.

Modulo 4, residues 0,1,2,3 have square residues 0,1,0,1. Thus x²+y² has only residues 0,1 or 2 modulo 4. It can never have residue 3. Therefore x²+y²=3 has no integer solution, although its real circle contains many points. The sixteen-cell residue grid checks every possible pair of residue classes, not every integer individually.

The same proof excludes x²+y²=N whenever N≡3 (mod 4). It gives a necessary condition, not a characterization of all representable N. Nor does a compatible cell itself give actual integers satisfying the original equality; it gives only compatible remainders. Use a separate construction or complete bounded argument to establish existence.

For example, x²=2 passes a square-residue test modulo 7: residues 3 and 4 both have square residue 2. But no integer square equals 2. If |x|≤1, then x²≤1; if |x|≥2, then x²≥4. These exhaust the integers. Passing this one modulus therefore does not establish solvability.

A proved bound can turn a search into a complete proof

For x²+y²=5, both squares are nonnegative, so x²≤5 and y²≤5. Hence integer solutions satisfy |x|≤2 and |y|≤2. Unlike an arbitrary plotting window, this bound is proved from the equation and cannot omit a solution.

The only squares in that range are 0,1 and 4. To sum to 5, one coordinate square must be 1 and the other 4. Thus the complete list is (±1,±2) and (±2,±1), with each sign independent: eight distinct ordered pairs. The equal-scale lattice picture and its exact table show all eight, while the continuous circle is only the real comparison.

For x²+y²=0, nonnegativity forces x=y=0. For a negative target there are no real or integer solutions. For x²+y²=2, the same bound gives only (±1,±1), four ordered pairs. These elementary cases do not amount to a general algorithm for every nonlinear Diophantine equation.

Separate a construction, a filter and an obstruction

For ax+by=c, first handle both-zero coefficients; otherwise compute the positive gcd and test divisibility. Construct one solution, state the complete integer family, then impose any count or interval restrictions. Check a final pair in the original equation, including its signs and domain.

For a linear congruence, require a positive modulus, use the same gcd test and reduce the modulus along with the common factor. State whether you are listing all integer solutions or their finitely many residue classes. For a nonlinear equation, a modular obstruction can rule out solutions; a passed test needs further reasoning.

Predict before revealing the explorer: will the linear equation have lattice points, will any meet the nonnegative restriction, how many residue classes will survive, or will the square-sum grid contain a compatible cell? Compare a solvable integer equation with an impossible count problem, and a modular impossibility with a complete bounded construction. The diagram’s finite limits never replace the general proof.

Worked examples

Try it yourself

1. The pair (1/2,1/2) satisfies 2x+2y=2. Does it solve the corresponding integer equation? Give its complete integer solution family.

   Show the answer and reasoning

   No. All integer solutions are (x,y)=(t,1−t), t∈ℤ.

   Both coordinates of the displayed pair are nonintegers. Divide the equation by 2 to get x+y=1; an arbitrary integer x=t determines y=1−t, and every such pair works.

2. Does 12x+18y=7 have an integer solution? Justify your answer for every possible integer pair.

   Show the answer and reasoning

   No integer solution exists.

   The gcd is 6. Every integer combination 12x+18y is a multiple of 6, whereas 7 is not. A search window is unnecessary.

3. Give all integer solutions of 6x+4y=2, starting from (1,−1). Explain the opposite signs in the step.

   Show the answer and reasoning

   (x,y)=(1+2t,−1−3t), t∈ℤ.

   The gcd is 2, so the step is (4/2,−6/2)=(2,−3). Its contributions 6×2+4×(−3)=0 cancel. The coprime-difference proof shows every integer solution is in this family.

4. Find all integer solutions of 0x−3y=6. Are any nonnegative in both coordinates?

   Show the answer and reasoning

   All pairs are (x,−2), x∈ℤ. None have both coordinates nonnegative.

   The equation fixes y=6/(−3)=−2 and does not restrict x. The count restriction on y fails for every free x.

5. Solve 0x+0y=0 and 0x+0y=−2 over integers. Can the first be described by a single line step?

   Show the answer and reasoning

   The first has every pair in ℤ²; the second has none. The first needs two independent integer choices, rather than one line parameter.

   The left side is always 0. A one-parameter line would omit integer points away from that line; dividing by gcd(0,0) would also be invalid.

6. Find the full integer family for 4x+6y=2 and decide whether any pair is nonnegative.

   Show the answer and reasoning

   The family is (−1+3t,1−2t), t∈ℤ; no nonnegative pair exists.

   The particular pair (−1,1) works. The coordinate bounds require t≥1 and t≤0 simultaneously, so their intersection is empty.

7. For −2x+3y=1, check whether the nonnegative solution list is finite. Give its exact parameter restriction.

   Show the answer and reasoning

   It is infinite: (x,y)=(1+3t,1+2t) for every integer t≥0.

   Both coordinates increase with t. Their lower bounds round up to 0, and neither gives an upper bound. A finite diagram cannot make the list finite.

8. Solve −3x≡1 (mod 7). Check the residue of the product at your answer.

   Show the answer and reasoning

   x≡2 (mod 7), equivalently x=2+7t for integer t.

   At x=2 the product is −6, whose normalized residue modulo 7 is 1. The gcd is 1, so there is one solution class. Adding 7 to x changes −3x by a multiple of 7.

9. A learner cancels 2 from 2x≡0 (mod 6) and writes x≡0 (mod 6). What is the correct conclusion and a counterexample to the learner’s claim?

   Show the answer and reasoning

   The equivalent result is x≡0 (mod 3). The integer x=3 solves the original but not the learner’s stronger congruence.

   Divisibility means 2x=6k. Dividing the equality by 2 gives x=3k, changing the modulus to 3. There are two classes modulo 6, namely 0 and 3.

10. Solve 0x≡0 (mod 5), 0x≡2 (mod 5), and 7x≡−2 (mod 1).

    Show the answer and reasoning

    The first and third have every integer x as a solution. The second has none.

    The first difference is 0, divisible by 5, while −2 is not divisible by 5. Modulus 1 divides every integer difference and has just the residue class 0.

11. Prove that x²+y²=11 has no integer solution without searching individual integers.

    Show the answer and reasoning

    There is no solution because 11≡3 (mod 4), which a sum of two integer squares cannot be.

    Each square has residue 0 or 1 modulo 4; their sums have residues 0,1,2. This exhaustive residue argument applies to every signed integer pair.

12. Both 3² and 4² have residue 2 modulo 7. Does this prove an integer solution of x²=2? Explain completely.

    Show the answer and reasoning

    No. There is no integer solution of x²=2.

    A compatible residue is only necessary. Integers with |x|≤1 have square at most 1; those with |x|≥2 have square at least 4. These cases leave no square equal to 2.

13. List every integer solution of x²+y²=2 and prove that the list is complete.

    Show the answer and reasoning

    The four pairs are (1,1),(1,−1),(−1,1),(−1,−1).

    Each coordinate has absolute value at most 1, since its square is at most 2. In that range, both squares must be 1 to sum to 2. Each coordinate can independently have either sign.

14. A plot contains no lattice points satisfying 6x+9y=5 inside [−6,6]². Which extra fact proves global impossibility?

    Show the answer and reasoning

    gcd(6,9)=3 does not divide 5.

    The picture checks only finitely many integer pairs. The divisibility fact excludes every pair in ℤ², inside and outside the window. An empty finite search alone would not do so.

What to carry forward

• For coefficients not both zero, ax+by=c is integer-solvable exactly when the positive gcd divides c.
• One particular solution plus the primitive step (b/g,−a/g) gives every integer solution; handle the both-zero plane separately.
• Count restrictions filter the integer parameter and may leave a finite, empty or unbounded set.
• A linear congruence has a complete family and a known class count; cancel the modulus along with a common factor.
• An impossible residue rules out integer solutions. A compatible residue or a finite plotting window needs additional reasoning to prove existence or completeness.