ℕ

Diophantine Equations

Undergraduate

Definition

Diophantine equations are polynomial equations seeking integer solutions. Key problems are existence and finding all solutions.

ax + by = c

Linear Diophantine equation

gcd(a,b) | c implies solution exists

Existence condition

xⁿ + yⁿ = zⁿ

Fermat's Last Theorem (no integer solutions for n≥3)

Example 1

Find integer solutions to 3x + 5y = 1.

Discovered by: Diophantus (c. 3rd century)

Diophantus of Alexandria studied these problems in his work 'Arithmetica'.

Extended Euclidean in RSA

Coin change problem