Diofantické rovnice jsou podurčené polynomiální rovnice, u kterých se hledá řešení v množině $\mathbb{Z}$.

Lineární diofantická rovnice je rovnice ve tvaru součtu dvou monomů prvního řádu:

$$ax+by=c\,.$$

Takovým rovnostem se také říká Bézoutovy. Lze je vyřešit pomocí rozšířeného Euklidova algoritmu.

K čemu se ale řešení takových rovnic hodí? Pojďme se podívat na jednu úlohu, která se objevila v matematickém testu pro čtvrtou třídu základní školy.

Mimoni založili orchestr. Umí hrát jen na basu nebo kytaru. Jejich basy mají 5 strun a jejich kytary mají 6 strun. Celkem mají nástroje v jejich orchestru 39 strun. Kolik Mimoňů hraje v orchestru?

Po přečtení by měl být každý schopen převést slovní vyjádření do matematické notace

$$5x+6y=39\,.$$

Žáci čtvrté třídy většinou neznají rozšířený Euklidův algoritmus. Naštěstí jsou zde malé koeficienty a s trochou pokusu a omylu by měli přijít na to, že řešením je $[x;y]=[3;4]$, neboli Mimoňů hraje v orchestru 7.

Pojďme si ale ukázat, jak by vypadalo obecné řešení, které lze aplikovat na podobné úlohy pro jakákoli čísla $a, b, c\in \mathbb{Z}$.

Bézoutova rovnost říká, že:

Nechť $c:=gcd(x,y)$, potom:

$$\forall x,y\in\mathbb{Z}\ \exists a,b\in\mathbb{Z}\colon ax+by=c\,.$$

Jelikož $gcd(5,6)=1$, naše rovnice má celočíselná řešení. Abychom je zjistili, musíme nejdříve nalézt řešení pro $5x+6y=gcd(5,6)=1$. K tomu lze využít Euklidův algoritmus.

1. $6=5(1)+1$
2. $5=1(5)+0$

Zpětným dosazením zjistíme, že $5(-1)+6(1)=1$. U tohoto triviálního příkladu je to zřejmé, ale u složitějších verzí je zpětné dosazování delší. Toto dosazování je právě rozšířením Euklidova algoritmu.

Nyní, když jsme nalezli řešení pro $5x+6y=1$, jednoduše vynásobíme celou rovnici tak, abychom na pravé straně dostali požadované $c$. V našem případě 39.

$$5(-39)+6(39)=39$$

Získali jsme tak jedno z řešení $[x_1;y_1]=[-39;39]\in K$. Všechna ostatní řešení mají následující tvar:

$$\bigg[x_1-r\frac{b}{gcd(a,b)}; y_1+r\frac{a}{gcd(a,b)}\bigg]\in K; r\in \mathbb{Z}\,,\\ [-39-6r;39+5r]\in K; r\in \mathbb{Z}\,.$$

Pro vyřešení původní úlohy musíme nalézt uspořádanou dvojici $[x;y]$ takovou, že $x>0\wedge y>0$. Toho lze jednoduše dosáhnout nerovnicemi.

$$-39-6r>0 \wedge 39+5r>0\,,\\ r<-\frac{13}{2} \wedge r>-\frac{39}{5}\,,\\ r<-6,5\wedge r>-7,8\,.$$

Jediné celé číslo vyhovující této nerovnici je $r=-7$. Po dosazení $r$ do vzorce dostáváme $[x;y]=[3;4]$.

Protože se jedná o algoritmus, jeho manuální exekuce je náchylná na chyby a často také fádní. Mnohem výhodnější je implementovat pro tento účel skript. Níže můžete vidět mé řešení v Pythonu. Pokud máte nějaké nápady na jeho vylepšení, můžete navštívit tento repozitář na GitHubu.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

def gcd(a, b):
  return a if b == 0 else gcd(b, a%b) 

def xgcd(a, b):
  x0, x1, y0, y1 = 0, 1, 1, 0
  while a != 0:
    q, b, a = b // a, a, b % a
    y0, y1 = y1, y0 - q * y1
    x0, x1 = x1, x0 - q * x1
  return b, x0, y0

def diophantine_values(r, g, a, b, x1, y1):
  return (x1-r*b/g,y1+r*a/g)

if __name__ == "__main__":
  print(gcd(24,16))
  print("Linear diophantine equation input form ax+by=c")
  a,b,c = [int(input(x+"=")) for x in "abc"]
  g, x, y = xgcd(a,b)
  if g % c != 0:
    print("There are no solutions")
  k = c / g
  x*=k
  y*=k
  print("Solution for r=0:")
  print(diophantine_values(0,g,a,b,x,y))
  while True:
    r=int(input("r="))
    print("Solution for r=" + str(r) + ":")
    print(diophantine_values(r,g,a,b,x,y))