Diophantine Equations and Fermat's Little Theorem

Equations that demand whole-number answers

A [[diophantine-equation|Diophantine equation]] is an ordinary equation, but we insist the solutions be integers. The simplest interesting case is the linear one, ax + by = c. Think of buying items: if pencils cost 4 coins and pens cost 6, can you spend exactly 30? You need whole numbers of each — fractional pencils are not allowed.

Here is the clean rule, straight from Bezout's identity: ax + by = c has integer solutions if and only if the greatest common divisor of a and b divides c. The GCD is the smallest positive amount a and b can build, so c must be a multiple of it.

Solve 4x + 6y = 30 in integers.

  gcd(4, 6) = 2, and 2 | 30 → solutions exist.
  Divide through by 2:  2x + 3y = 15.

One solution by inspection: x = 3, y = 3
  (since 2·3 + 3·3 = 6 + 9 = 15). ✓

General solution (k any integer):
  x = 3 + 3k,   y = 3 − 2k.
Check k = 1:  2(6) + 3(1) = 12 + 3 = 15. ✓

Because gcd(4,6)=2 divides 30, solutions exist; one particular solution generates them all.

Fermat's little theorem

Our finale is a gem from the 1600s. [[fermats-little-theorem|Fermat's little theorem]] says: if p is a prime and a is not divisible by p, then a^(p−1) ≡ 1 (mod p). Raising any number to the power one-less-than-the-prime, then reducing, always lands you back on 1. A handy companion form, valid for every integer a, is a^p ≡ a (mod p).

Check with p = 7, a = 3:
  3^(7−1) = 3^6 = 729
  729 = 7 · 104 + 1  →  3^6 ≡ 1 (mod 7) ✓

Now use it to find 3^100 (mod 7) the fast way:
  By Fermat, 3^6 ≡ 1 (mod 7).
  100 = 6·16 + 4, so
  3^100 = (3^6)^16 · 3^4 ≡ 1^16 · 3^4 (mod 7)
  3^4 = 81 = 7·11 + 4 ≡ 4 (mod 7)
  Therefore 3^100 ≡ 4 (mod 7).

Fermat's theorem turns a 48-digit power into a one-line remainder computation.

Notice how everything connects: the theorem is stated with modular arithmetic, its hypothesis (a not divisible by p) is a relatively prime condition, and we exploit it by writing the exponent through the division algorithm as 100 = 6·16 + 4. The whole track has been quietly assembling these tools.

Why these results matter

These are not museum pieces. Fermat's little theorem is the seed of fast primality tests and of the RSA cryptosystem that secures the internet; linear Diophantine equations underlie scheduling, gear ratios, and making change. From the plain idea of one integer dividing another, you have arrived at the working tools of modern mathematics.