Diofantske jednadžbe (lakša grupa)

Zadaci

Diofantske

Dodatna 2. razred (GLV)

Linearna diofantska jednadžba (primjer)

Teorem 1 (Homogena linearna diofantska jednadžba): Diofantska jednadžba oblika $ax + by = 0$ gdje su $a, b\in \mathbb{Z}$ , $a \neq 0, b \neq 0$ ima beskonačno mnogo cjelobrojnih rješenja, takvih da su $(x, y) = \left(\dfrac{tb}{M(a, b)}, \dfrac{-ta}{M(a, b)} \right), \ t \in \mathbb{Z}$

Teorem 2 (Linearna diofantska jednadžba): Diofantska jednadžba oblika $ax + by = c$ gdje su $a, b, c \in \mathbb{Z}$ , $a \neq 0, b \neq 0$ ima cjelobrojna rješenja ako i samo ako $M(a, b)$ dijeli $c$ . Tada ih ima beskonačno mnogo. Također, sva su rješenja oblika zbroja jednog partikularnog i skupa rješenja homogenog.

PRIMJER 1:

Riješimo homogenu diofantsku jednadžbu $3x + 5y = 0$ .

RJEŠENJE:

Izrazimo jednu nepoznanicu pomoću druge: $3x = -5y$ . Budući da je $x$ cijeli broj, $y$ mora biti djeljiv s 3, tj. $y$ je oblika $y = 3t$ gdje je $t$ neki cijeli broj. Iz toga dobivamo da je $x = -5t$ . Dobili smo da su rješenja početne jednadžbe svi uređeni parovi $(-5t, 3t)$ , $t \in \mathbb{Z}$ .

PRIMJER 2:

Riješimo diofantsku jednadžbu $3x + 5y = 7$ .

RJEŠENJE:

Pokušajmo pronaći neki par $(x_0, y_0)$ koji zadovoljava jednadžbu. Pogađanjem možemo naći uređen par $(-1, 2)$ što nam je zapravo jedno partikularno rješenje naše diofantske jednadžbe.

Promatrajmo sada homogenu jednadžbu 3x + 5y = 0. Iz prethodnog primjera znamo da su rješenja te jednadžbe svi uređeni parovi $(-5t, 3t)$ , gdje je $t \in \mathbb{Z}$ .
Iz Teorema 1.3. zaključujemo da su rješenja opće jednadžbe parovi $(-1 - 5t, 2 + 3t),\ t \in \mathbb{Z}$ .

Zadatci za samostalno rješavanje

1. Riješi homogenu diofantsku jednadžbu: $4x - 10y = 0$ .

2. Riješi diofantsku jednadžbu: $6x - 10y = 8$ .

3. Riješi diofantsku jednadžbu: $9999x - 99999y = 37373747$ .

Metoda faktorizacije (primjer)

Lema 1: Umnožak faktora je nula ako i samo ako je barem jedan od faktora nula.

PRIMJER 1:

Riješi diofantsku jednadžbu: $(x+3)(y-7)(x+y)=0$ .

RJEŠENJE:

Po lemi, vidimo da su rješenja oblika $x=-3, y \in \mathbb{Z}$ (ako je prva zagrada jednaka nuli), $x \in \mathbb{Z}, y=7$ (ako je druga zagrada jednaka nuli) i $x = -y$ (ako je treća zagrada jednaka nuli; ovo možete zapisati i preko nekog parametra).

Nema veze što se neki skupovi rješenja preklapaju, na primjer $(x, y) = (-3, 3)$ (kada su prva i treća zagrade jednake nuli), bitno je samo da pokrijete sva rješenja.

PRIMJER 2:

Riješimo diofantsku jednadžbu $xy + x - 3y - 6 = 0$ .

RJEŠENJE:

Zadana jednadžba zapravo je jednaka: $(y + 1)(x - 3) = 3$ . Dakle, dovoljno je riješiti samo slučajeve kada je jedna zagrada jednaka $\pm 1$ , a druga $\pm 3$ . Sada izjednačavamo zagrade s tim vrijednostima. Konkretno, rješenja su $(x, y) = (2, 4), (0, 6), (-4, 2), (-2, 0)$ .

Zadatci za samostalno rješavanje

1. Riješi u cijelim brojevima: $4x^2 + 2xy + 2x + y = 0$ .

2. Riješi u cijelim brojevima: $6x^2 - 13xy + 6y^2 = 4$ .

3. Nađi sva cijelobrojna rješenja za: $x^2 + 37^2 = y^2$ .

Metoda kvocijenta (primjer)

Cilj metode kvocijenata je izraziti jednu nepoznanicu u potpunosti preko druge, i onda komentirati slučajeve kada je izraz cijeli broj.

Lema 1(Zatvorenost na zbrajanje i oduzimanje): Skup cijelih brojeva zatvoren je i s obzirom na zbrajanje i oduzimanje, tj. ukoliko cijelom broju oduzmemo ili pribrojimo drugi cijeli broj, rezultat će i dalje biti cijeli broj. Specijalan slučaj ovoga je: $A \pm \frac{B}{P(x)} \in \mathbb{Z} \Longrightarrow \frac{B}{P(x)} \in \mathbb{Z} \Longrightarrow P(x) \mid B$

PRIMJER 1:

Riješi diofantsku jednadžbu $xy + 2y = x$ .

RJEŠENJE:

$y(x+2) = x \Longleftrightarrow y = \dfrac{x}{x+2} = 1 - \dfrac{2}{x + 2}$ . Sada vidimo da je $x + 2 \in (1, -1, 2, -2)$ jer mora biti djelitelj od 2 kako bi razlomak bio cjelobrojan, pa je $x \in \{-1, -3, 0, -4\}$ i (daljnjim uvrštavanjem) $y \in \{-1, 3, 0, 2\}$ .

PRIMJER 2:

Riješi diofantsku jednadžbu: $xy + 3y^2 = 11$

RJEŠENJE:

$xy = -3y^2 + 11 \Longleftrightarrow x = \dfrac{-3y^2 + 11}{y}= -3y + \dfrac{11}{y}$ pa je $y \in \{1, -1, 11, -11\}$ , što daje rješenja redom $x \in \{8, -8, -32, 32\}$ .

Zadatci za samostalno rješavanje

1. (Školsko 2019. SŠ1 5.) Odredi sve parove $(m, n)$ cijelih brojeva za koje vrijedi $mn + 5m + 2n = 121$

2 (Državno 1998. SŠ1 2.) Nađite sve prirodne brojeve $m$ i $n$ koji zadovoljavaju jednadžbu: $10(m + n)=mn$

Metoda posljednje znamenke (primjer)

Metoda posljednje znamenke je samo poseban slučaj metode kongruencija kojom ćemo se pozabaviti neki drugi put koristeći kao uvod predavanje s ovogodišnje Ljetne škole: https://drive.google.com/drive/folders/170lvUaNcIh_BsNTtRsrZHARXhKRW2-4t?usp=sharing

PRIMJER 1:

Riješi diofantsku jednadžbu $x^2 + 10y = 1234567$ .

RJEŠENJE:

Kvadrat cijelog broja može završavati jednom od znamenaka 0, 1, 4, 5, 6 ili 9. S obzirom da $10y$ završava znamenkom 0, zadnja znamenka od $x^2+10y$ može biti 0, 1, 4, 5, 6 ili 9. Kako broj s desne strane jednakosti završava znamenkom 7, zadana jednadžba nema cjelobrojnih rješenja.

PRIMJER 2:

Riješimo diofantsku jednadžbu $x^2 + 5y = 37191834641769123$ .

RJEŠENJE:

Budući da kvadrat cijelog broja završava sa znamenkom 0, 1, 4, 5, 6, ili 9,a broj $5y$ sa znamenkom 0 ili 5, slijedi da zbroj na lijevoj strani završava s 0, 1, 4, 5, 6, ili 9, a nikako s 3. Dakle, zadana diofantska jednadžba nema rješenja.

Zadatci za samostalno rješavanje

1. Nađi sve parove prirodnih brojeva $(a, b)$ takvih da vrijedi: $6^a + 5^b = 3737 \dots 3747 \hspace{10mm} \text{(ukupno 37 puta se ponavlja 37).}$

2. Nađite cjelobrojna rješenja jednadžbe: $5^x + y^4 = 194482$ .

Metoda nejednakosti (primjer)

U metodi nejednakosti, želimo ograničiti broj mogućnosti tako da najprije ograničimo neku nepoznanicu pomoću nejednakosti. Zatim nam ostaje relativno malo primjera koje možemo provjeriti ručno i vidjeti ima li rješenja.

PRIMJER:

U skupu prirodnih brojeva riješite jednadžbu $a + b + c = abc$ .

RJEŠENJE:

Pošto je jednadžba potpuno simetrična, bez smanjenja općenitosti neka je $a \leq b \leq c$ . Tada je $abc = a + b + c \leq 3c$ , odnosno $ab \leq 3$ (kako je $c \in \mathbb{N}$ , smijemo nejednakost podijeliti s $c$ ) , pa razlikujemo tri slučaja: $\begin{enumerate} \item $a = 1, b = 1$ (uvrštavanjem te vrijednosti u početnu jednadžbu dobijemo kontradikciju $2 = 0$); \item $a = 1, b = 2$ (dobivamo $c = 3$); \item $a = 1, b = 3$ (dobivamo $c = 2$ što je kontradikcija s $b \leq c$). \end{enumerate}$ Dakle, jedino rješenje je $(1, 2, 3)$ i sve permutacije tog skupa.

PRIMJER:

Dokažite da izraz $n^2 + n + 1$ , gdje je $n \in \mathbb{N}$ , ne može biti kvadrat cijelog broja.

RJEŠENJE:

Metoda koju ćemo primijeniti poznata je i kao smještanje među kvadrate, tj. pokazujemo da broj ne može biti kvadrat tako da ga smjestimo između dva uzastopna kvadrata.

Primijetimo da zbog $n \in \mathbb{N}$ tj. $n > 0$ vrijedi $n^2 + n + 1 > n^2 + 0 + 1 > n^2$ . S druge strane, slično zaključujemo i $n^2 + n + 1 < (n^2 + n + 1) + n = n^2 + 2n + 1 = (n + 1)^2$ . No kako su $n$ i $n + 1$ su 2 uzastopna prirodna broja, a $n^2 + n + 1$ strogo između njihovih kvadrata, taj broj nikako ne može biti kvadrat nekog prirodnog broj.