Linear Diophantine Equations

Intro to Proofs · Axiom Academy

Making exact change is secretly a number-theory question. One rule — does divide c ? — decides whether ax + by = c can be solved in whole numbers, and the Extended Euclidean Algorithm builds the answer. A vending machine wants exact change and takes only nickels and dimes — can you hit the price on the nose? That's a linear Diophantine equation ax + by = c , and three moves crack it. Drag the target amount. Nickels (5 ) and dimes (10 ) only reach multiples of 5 — so the equation 5x + 10y = c has whole-number solutions exactly when divides c . Build the solution with the Euclidean Algorithm Switch to 3 and 5 coins — now , which divides everything , so every target is reachable. Drag c and watch the Extended Euclidean Algorithm construct the actual x threes and y fives that hit it. One solution means infinitely many Fix the target at 30 . Slide the parameter t : every step trades 5 threes for 3 fives, so marches through all integer solutions — the green band marks the ones you can pay with real coins. Three moves on one equation: test it ( decides if a solution exists), build it (Extended Euclid constructs one), walk it ( gives them all). The same logic balances chemical equations , schedules events on different cycles , and finds the modular inverses behind RSA cryptography.

This is the written version of the interactive lesson above. See the full Intro to Proofs course.