Diophantine Equations

Diophantine equations are polynomial equations for which only integer or rational solutions are sought.

Linear Diophantine Equations

A linear Diophantine equation has the form $ax + by = c$. This has integer solutions if and only if $\gcd(a, b)$ divides $c$.

def extended_gcd(a, b):
  if a == 0: return b, 0, 1
  gcd, x1, y1 = extended_gcd(b % a, a)
  x = y1 - (b // a) * x1
  y = x1
  return gcd, x, y

def solve_linear_diophantine(a, b, c):
  gcd, x0, y0 = extended_gcd(a, b)
  if c % gcd != 0:
      return None, "No solution"
  m = c // gcd
  return (x0 * m, y0 * m), f"gcd({a}, {b}) = {gcd}"

# Solve 12x + 15y = 9
print(f"Solution to 12x + 15y = 9: {solve_linear_diophantine(12, 15, 9)}")
# Solve 12x + 15y = 10
print(f"Solution to 12x + 15y = 10: {solve_linear_diophantine(12, 15, 10)}")

Pythagorean Triples

The equation $x^2 + y^2 = z^2$ is one of the most famous Diophantine equations. Primitive solutions can be generated using Euclid’s formula: $x = m^2 - n^2, y = 2mn, z = m^2 + n^2$ for $m > n > 0$.

def generate_pythagorean_triples(limit):
  triples = []
  for m in range(2, int(limit**0.5) + 2):
      for n in range(1, m):
          x = m**2 - n**2
          y = 2 * m * n
          z = m**2 + n**2
          if z <= limit:
              triples.append((x, y, z))
  return triples

print(f"Triples up to 30: {generate_pythagorean_triples(30)}")

Fermat’s Last Theorem

Fermat’s Last Theorem states that $x^n + y^n = z^n$ has no positive integer solutions for $n > 2$. This was conjectured by Pierre de Fermat in 1637 and finally proven by Andrew Wiles in 1994 using the theory of modular forms.

Elliptic Curves

Diophantine equations of the form $y^2 = x^3 + ax + b$ are known as Elliptic Curves. They have profound applications in modern cryptography and were crucial in the proof of Fermat’s Last Theorem.