Diofantska jednačina

Diofantska linearna jednačina je jednačina oblika:

${\displaystyle ax+by=c}$ 

gdje su a, b i c neki cijeli brojevi.

Primjer

${\displaystyle x=-{\frac {5}{3}}y}$ 

Kako je x cio broj to je y djeljivo sa 3

${\displaystyle y=3t}$ 

odnosno

${\displaystyle x=-5t}$ 

${\displaystyle (x,y)=(-5t,3t)}$ 

Teorema

1. Diofantska jednačina ${\displaystyle ax+by=c}$  , gdje su ${\displaystyle a}$ ,${\displaystyle b}$ ,${\displaystyle c}$  cijeli brojevi ${\displaystyle a^{2}+b^{2}\neq ,}$  ima cjelobrojna rješenja ako i samo ako ${\displaystyle M(a,b)}$  dijeli ${\displaystyle c}$ .
2. Ako su ${\displaystyle x_{0}}$  i ${\displaystyle y_{0}}$  rješenja te jednačine onda su sva rješenja oblika

${\displaystyle x=x_{0}+{\frac {b}{d}}t}$ 

${\displaystyle y=y_{0}+{\frac {a}{d}}t}$ 

Rješenje ${\displaystyle (x_{0},y_{0})}$  naziva se partikularno rjesenje diofantske jednacine. Op ste rjesenje je zbir partikularnog rjesenja i rjesenja homogene jednacine ${\displaystyle ax+by=0}$ 

Primjer

${\displaystyle 3x+5y=8}$ 

Partikularno rješenje je ${\displaystyle (1,1)}$ , a rješenja pripadne homogene jednačine su ${\displaystyle (-5t,3t)}$ , ${\displaystyle t\in Z}$ 

Rješenja jednačine su parovi ${\displaystyle (1-5t,1+3t)}$  za ${\displaystyle t\in Z}$ 

Za pronalaženje partikularnog rješenje diofantske jednačine korististimo Euklidov algoritam pomoću kojeg određujemo cijele brojeve ${\displaystyle k}$  i ${\displaystyle l}$  za koje vrijedi ${\displaystyle ax+by=d}$  gdje je ${\displaystyle d=M(a,b)}$ , a zatim množenjem sa ${\displaystyle {\frac {c}{d}}}$  dobijamo partikularno rješenje.

Primjer

${\displaystyle 1000x-123y=5}$ 

${\displaystyle 1000=8*123+16}$ 

${\displaystyle 123=7*16+11}$ 

${\displaystyle 16=1*11+5}$ 

${\displaystyle 11=2*5+1}$ 

pa je

${\displaystyle 16=1000-8*123}$ 

1${\displaystyle 1=123-7*16}$ 

${\displaystyle 5=16-1*11}$ 

${\displaystyle 1=11-2*5}$ 

U posljednju jednakost uvrstimo izraz za broj 5 iz pretposljednje jednakosti

${\displaystyle 1=11-2*5=11-2*(16-11*1)=3*11-2*16}$ 

${\displaystyle 1=3*(123-16*7)-2*16=3*123-23*16}$ 

${\displaystyle 1=3*123-23*(1000-8*123)=-23*1000+187*123}$ 

tj.

${\displaystyle 1=-23*1000+187*123}$  ${\displaystyle /*5}$ 

${\displaystyle 5=-115*1000+935*123}$ 

${\displaystyle x_{0}=-115}$ 

${\displaystyle y_{0}=-935}$ 

${\displaystyle x=123t}$ 

${\displaystyle y=1000t}$ 

Rješenje date jednadnacine je

${\displaystyle x=-115+123t}$ 

${\displaystyle y=-935+1000t}$  ${\displaystyle t\in Z}$ 

Primjer

Za prevoz neke robe raspolažemo vrećama od 40 kg i 60 kg. Koliko treba uzeti jednih, a koliko drugih da se prevese 500 kg robe

Zadatak ćemo riješiti Eulerovom metodom

${\displaystyle 40x+60y=500}$ 

${\displaystyle 2x+3y=25}$  za ${\displaystyle x\geq 0}$  i ${\displaystyle y\geq 0}$ 

${\displaystyle x={\frac {25-3y}{2}}=12-y+{\frac {1-y}{2}}}$ 

${\displaystyle {\frac {1-y}{2}}=u}$  ${\displaystyle u\ Z}$ 

${\displaystyle 2u+y=1}$ 

${\displaystyle y=1-2u}$ 

${\displaystyle x=12-(1-2u)+u=11+3u}$ 

Rješenja jednadčine su parovi ${\displaystyle (x,y}$ ) gdje je ${\displaystyle x=11+3u}$  i ${\displaystyle y=1-2u}$ 

${\displaystyle -{\frac {1}{3}}\leq u\leq {\frac {1}{2}}=>u=-3,-2,-1,0}$ 

Traženi parovi ${\displaystyle (x,y}$ ) su ${\displaystyle (2,7)}$  ${\displaystyle (5,5)}$  ${\displaystyle (8,3)}$  i ${\displaystyle (11,1)}$ 

Ne postoji univerzalna metoda rješavanja ovih jednačina ali zato postoji niz metoda kojima rješavamo neke specijalne tipove nelinearnih diofantskih jednačina. Neke od tih metoda su:

1. metoda faktorizacije
2. metoda razlomka
3. metoda posljednje cifre
4. metoda kongruencije
5. metoda zbira potencija s parnim eksponentima
6. metoda nejednakosti

Metoda faktorizacije sastoji se u tome da se jedna strana jednačine zapiše u obliku proizvoda cjelobrojnih vrijednosti, pa uzimajući u obzir drugu stranu jednačine posmatramo moguće slučajeve.

${\displaystyle xy+x-3y-3=0}$ 

(${\displaystyle x-3)(y+1)=3}$ 

Ovo je moguće za

x-3	y+1
1	3
-1	-3
3	1
-3	-1

odnosno

x	y
4	2
2	-4
6	0
0	-2

Osnovna ideja ove metode slična je kao kod metode faktorizacije, samo što sada jednu stranu jednačine zapisujemo u obliku razlomka dvaju cjelobrojnih vrijednosti, dok s druge strane jednačine imamo također cjelobrojnu vrijednost. Zbog toga nazivnik tog razlomka mora dijeliti brojnik, što nam daje klasifikaciju mogućih slučajeva. Spomenuti razlomak u praksi najčešće dobijemo tako da se jedna nepoznata izrazi kao racionalna funkcija druge.

${\displaystyle xy+2y=x}$ 

${\displaystyle y(x+2)=x}$ 

${\displaystyle y={\frac {x}{4x+2}}=1-{\frac {2}{x+2}}}$ 

${\displaystyle x\ {\begin{Bmatrix}-1,-3,0,-4\end{Bmatrix}}}$ 

${\displaystyle y\ {\begin{Bmatrix}-1,3,0,-2\end{Bmatrix}}}$ 

Metoda posljednje cifre je podmetoda metode ostataka koja koristi ispitivanje ostataka pri dijeljenju brojem 10. Preciznije, razdvajanje slučajeva se vrši posmatranjem zadnje cifre nekih dijelova jednačine, te njihovim usklađivanjem.

${\displaystyle x^{2}+5y=199519941993}$ 

Kvadrat cijelog broja završava cifrom 0,1,4,5,6,ili 9, a broj ${\displaystyle 5y}$  sa 0 ili 5, pa zbir na lijevoj strani završava s 0,1,4,5,6, ili 9, a ne sa 3. Jednačina nema rješenja.

${\displaystyle x^{2}-4y=1995}$ 

${\displaystyle 1995}$  neparan a ${\displaystyle 4y}$  paran pa je ${\displaystyle x}$  neparan

${\displaystyle x=2k-1}$ 

${\displaystyle (2k-1)^{2}-4y=1995}$ 

${\displaystyle 4k^{2}-4k+1-4y=1995}$ 

${\displaystyle 4(k^{2}+k-y)=1994}$ 

Jednačina nema rješenja jer 1995 nije djeljivo sa 4

Metoda zbira je slična metodi faktorizacije, samo što sada jednu stranu jednačine zapisujemo u obliku zbira (najčešće nenegativnih) cijelih brojeva, te dalje diskutujemo slučajeve koji mogu nastupiti.

${\displaystyle x^{2}+y^{2}+2x-4y+8=0}$ 

${\displaystyle (x+1)^{2}+(y-2)^{2}=13}$ 

${\displaystyle (x+1)^{2}=9}$ 

${\displaystyle (y-2)^{2}=4}$ 

${\displaystyle (x,y)\in {\begin{Bmatrix}(1,5),(2,4)\end{Bmatrix}}}$ 

Ova metoda se često koristi da bi se smanjio skup mogućih rješenja date jednačine, a zatim se na tom smanjenom skupu razlikuju slučajevi. Na tom smanjenom skupu razlikuju se slučajevi. Metoda nejednakosti se često koristi i u kombinaciji s nekom drugom metodom za rješavanje nelinearnih diofantskih jednačina

${\displaystyle 3^{x}+4^{x}=5^{x}}$ 

${\displaystyle x=2}$ 

${\displaystyle 3^{x}+4^{x}=5^{x}}$  ${\displaystyle /:5^{x}}$ 

${\displaystyle ({\frac {3}{5}})^{x}+({\frac {4}{5}})^{x}=1}$ 

za ${\displaystyle x<2}$ 

${\displaystyle ({\frac {3}{5}})^{x}+({\frac {4}{5}})^{x}>1}$ 

za ${\displaystyle x>2}$ 

${\displaystyle ({\frac {3}{5}})^{x}+({\frac {4}{5}})^{x}<1}$ 

Jednačina ima samo jedno rjesenje ${\displaystyle x=2}$ 

Neka je zadana jednacina

${\displaystyle x^{2}+y^{2}=z^{2}}$ 

Uređenu trojku (x,y,z) koja zadovoljava zadanu jednačinu nazivamo Pitagorina trojka

Ako su brojevi x y z relativno prosti onda je to primitivna Pitagorina trojka

U svakoj primitivnoj Pitagorinoj trojci tačno je jedan od brojeva ${\displaystyle x}$ ,${\displaystyle y}$  neparan. Za ${\displaystyle x}$ ,${\displaystyle y}$ 

parne nebi se radilo o primitivnoj Pitagorinoj trojci

Diofantska jednačina oblika

${\displaystyle x^{2}-dy^{2}=a}$  gdje je ${\displaystyle d\in N}$  i nije potpun kvadrat je Pelova jednačina.

Pelova jednačina ima beskonačno mnogo rješenja u skupu prirodnih brojeva. Ako pronađemo najmanje (osnovno) rješenje ${\displaystyle (x_{e},y_{e})}$ , preostala rješenja ${\displaystyle (x_{n},y_{n})}$  možemo generisati na sljedeći načine

1. :${\displaystyle x_{n}+y_{n}{\sqrt {d}}}$  ${\displaystyle =(x_{n}+y_{n}{\sqrt {d}})^{n}}$ 
2. :${\displaystyle x_{n+1}=2x_{n}x_{e}-x_{n-1}}$  i ${\displaystyle y_{n+1}=2x_{n}y_{e}-y_{n-1}}$  za ${\displaystyle (x_{0},y_{0})=(1,0)}$  i ${\displaystyle (x_{1},y_{1})=(x_{e},y_{e})}$ 
3. :${\displaystyle x_{n+1}=x_{e}x_{n}+y_{e}dy_{n}}$  i ${\displaystyle y_{n+1}=x_{e}y_{n}+y_{e}dx_{n}}$ 

Jednačina

${\displaystyle x^{2}-dy^{2}=1}$  je Pellovska jednačina (jednačina Pellovog oblika)

Za razliku od Pellove jednačine ova jednačina nema uvijek cjelobrojno rješenje. ^[1]

Hipotezom je pretpostavljeno da za sve prirodne brojeve ${\displaystyle n\geq 2}$  postoji racionalni broj ${\displaystyle 4/n}$  koji se može iskazati kao zbir tri jedinična razlomka s pozitivnim, cjelobrojnim nazivnicima kako slijedi:

${\displaystyle {\frac {4}{n}}={\frac {1}{x}}+{\frac {1}{y}}+{\frac {1}{z}}.\,}$ 

Primjer

za ${\displaystyle n=1801}$ , postoji rješenje jednacie gdje je ${\displaystyle x=451}$ , ${\displaystyle y=295364}$  i ${\displaystyle z=3249004}$ .

Pomnožimo li obe strane jednačine s ${\displaystyle nxyz}$ , nalazimo Diofantsku jednačinu oblika:

${\displaystyle 4xyz=n(xy+xz+yz).\,}$  ^[2]

DIOFANTSKE JEDNADZBE/https: Arhivirano 11. 6. 2012. na Wayback Machine

1. ^ "Diofantske jednadžbe // Pellove i pellovske jednadžbe" (PDF). Arhivirano s originala (PDF), 8. 4. 2016. Pristupljeno 9. 3. 2016.
2. ^ 4-parametrowa seria rozwiązań równania Erdősa-Strausa