Diofantska jednačina

Diofantska jednačina je algebarska jednačina s dvije ili vise nepoznatih s cjelobrojnim koeficijentima u kojoj se traže cjelobrojna ili racionalna rješenja. Ime je dobila po Diofantu koji je prvi sistematski proučavao takve jednačine

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