A brief note on Diophantine Equations and Pythagorean Triples . Read it before a test. Try each question at the end before you open its answer.
Linear equations Solvable: a x + b y = c ax + by = c a x + b y = c has integer solutions exactly when d = gcd ( a , b ) ∣ c d = \gcd(a, b) \mid c d = g cd( a , b ) ∣ c . All solutions: x = x 0 + b d t x = x_0 + \frac{b}{d}t x = x 0 + d b t , y = y 0 − a d t y = y_0 - \frac{a}{d}t y = y 0 − d a t . Positive solutions: turn x > 0 x > 0 x > 0 and y > 0 y > 0 y > 0 into bounds on t t t . Coins: for coprime a , b a, b a , b the largest amount not payable is a b − a − b ab - a - b ab − a − b ; ( a − 1 ) ( b − 1 ) 2 \frac{(a-1)(b-1)}{2} 2 ( a − 1 ) ( b − 1 ) amounts are not payable. Pythagorean triples Primitive: m 2 − n 2 m^2 - n^2 m 2 − n 2 , 2 m n 2mn 2 mn , m 2 + n 2 m^2 + n^2 m 2 + n 2 with m > n m > n m > n coprime, of opposite parity. All: multiples of primitive ones. Divisibility: 60 ∣ a b c 60 \mid abc 60 ∣ ab c . Given leg a a a : factor a 2 = ( c − b ) ( c + b ) a^2 = (c - b)(c + b) a 2 = ( c − b ) ( c + b ) , both factors of the same parity. Other methods Factoring: make a product equal to a known number, such as ( x − p ) ( y − q ) = p q (x - p)(y - q) = pq ( x − p ) ( y − q ) = pq . Bounding: order the unknowns and trap the smallest. Remainders: squares modulo 4 4 4 or 8 8 8 , cubes modulo 7 7 7 or 9 9 9 . Pell: x 2 − d y 2 = 1 x^2 - dy^2 = 1 x 2 − d y 2 = 1 has all solutions from powers of x 1 + y 1 d x_1 + y_1\sqrt d x 1 + y 1 d . A worked example Find the non-negative solutions of 4 x + 9 y = 100 4x + 9y = 100 4 x + 9 y = 100 .
Condition. 9 y ≡ 100 ( m o d 4 ) 9y \equiv 100 \pmod 4 9 y ≡ 100 ( mod 4 ) , so y ≡ 0 ( m o d 4 ) y \equiv 0 \pmod 4 y ≡ 0 ( mod 4 ) . List. y = 0 , 4 , 8 y = 0, 4, 8 y = 0 , 4 , 8 give x = 25 , 16 , 7 x = 25, 16, 7 x = 25 , 16 , 7 . Check. 4 × 7 + 9 × 8 = 28 + 72 = 100 4 \times 7 + 9 \times 8 = 28 + 72 = 100 4 × 7 + 9 × 8 = 28 + 72 = 100 . Practice with new numbers
A program to try The program checks three facts by a search.
Read it first. Then run it. Do the lists agree with the worked example and the methods?
1. Change the leg 21 21 21 to 28 28 28 . How many triangles appear?
Mistakes to avoid Forgetting the gcd test. Mixing positive and non-negative. Factor pairs of different parity in x 2 − y 2 = n x^2 - y^2 = n x 2 − y 2 = n . Forgetting negative factor pairs when integer solutions are asked. Check yourself Does 12 x + 18 y = 50 12x + 18y = 50 12 x + 18 y = 50 have integer solutions? Stuck? Show a hint Show the answerWhich primitive triple comes from m = 6 m = 6 m = 6 , n = 5 n = 5 n = 5 ? Stuck? Show a hint Show the answerSolve ( x − 2 ) ( y − 4 ) = 3 (x - 2)(y - 4) = 3 ( x − 2 ) ( y − 4 ) = 3 in positive integers. Stuck? Show a hint Show the answerFind the second solution of x 2 − 3 y 2 = 1 x^2 - 3y^2 = 1 x 2 − 3 y 2 = 1 from ( 2 , 1 ) (2, 1) ( 2 , 1 ) . Stuck? Show a hint Show the answerSources David M. Burton, Elementary Number Theory , Chapters 2, 12 and 15.