Vrijeme: 11:39

Modularna aritmetika u diofantskim jednadžbama - Primjer 3

Primjer.

Odredite prirodne brojeve m za koje je 2^m-63 potpun kub prirodnog broja.

Rješenje.

Zapišimo prvo ovaj uvjet jednadžbom 2^m - 63 = n^3. Brojevi m i n su prirodni. Ako bude bilo bitno, primijetite da možemo zaključiti da je m \geq 6, jer je inače lijeva strana negativna.

Ponovno pogledajmo jednadžbu modulo neki N. Iz uputa s početka, zbog člana 2^m mogli bismo gledati jednadžbu modulo 4 ili 8, no nećemo se usrećiti budući da n^3 može davati razne ostatke pri dijeljenju s tim brojevima. No, n^3 je potpun kub, pa ima smisla gledati ostatke modulo 7.

Desna strana daje ostatke 0, 1 ili 6 pri dijeljenju sa 7. Broj 63 djeljiv je sa 7, dok izraz 2^m podijeljen sa 7 za razne m=1,2,3,\dots daje ostatke 2, 4, 1, 2, 4, 1, \dots. Da bi jednadžba bila zadovoljena, mora postojati neki izbor ostataka takav da se ostatci na lijevoj i desnoj strani poklapaju. Jedini izbor je kada oba izraza n^3 i 2^m daju ostatak 1 pri dijeljenju sa 7. Dok za n ne saznajemo mnogo (preciznije, možemo samo zaključiti da to znači da n daje ostatak 1, 2 ili 4 pri dijeljenju sa 7), za 2^m primjećujemo da se ostatak 1 pojavljuje na svakom trećem mjestu u nizu ostataka 2, 4, 1, 2, 4, 1, \dots koje 2^m daje podijeljen sa 7. Zato možemo zaključiti da je m nužno djeljiv s 3, odnosno možemo pisati m=3k, za neki prirodan broj k.

To je mnogo slabiji zaključak nego u prošlom primjeru u vidu da nismo zadatak reducirali na konačno mnogo slučajeva koje treba provjeriti. Samo smo zaključili da je m djeljiv s 3. No, i to je veliki korak, kada se sjetimo drugih tehnika za rješavanje diofantskih jednadžbi.

Uvrstimo ovaj zaključak u početnu jednadžbu: 2^{3k} - 63 = n^3. Na obje strane jednadžbe imamo potpun kub. Kada zapišemo jednadžbu drugačije, možemo iskoristiti razliku kubova i faktorizirati izraz: 63 = 2^{3k} - n^3 = (2^k - n) (2^{2k} + n \cdot 2^k + n^2 ). Slijeve strane imamo broj 63 koji nudi konačno mnogo različitih faktorizacija: 1\cdot 63, \ 3 \cdot 21, \ 7 \cdot 9, 9\cdot 7, \ 21 \cdot 3, \ 63 \cdot 1 .

Zato imamo šest mogućih podslučajeva: \begin{itemize} \item $2^k - n = 1$, $2^{2k} + n \cdot 2^k + n^2 = 63$; \item $2^k - n = 3$, $2^{2k} + n \cdot 2^k + n^2 = 21$; \item $2^k - n = 7$, $2^{2k} + n \cdot 2^k + n^2 = 9$; \item $2^k - n = 9$, $2^{2k} + n \cdot 2^k + n^2 = 7$; \item $2^k - n = 21$, $2^{2k} + n \cdot 2^k + n^2 = 3$; \item $2^k - n = 63$, $2^{2k} + n \cdot 2^k + n^2 = 1$. \end{itemize}

Za svaku od tih kombinacija treba provjeriti vodi li ka rješenju za neke prirodne k i n.

U prvom slučaju bismo iz prve jednakosti imamo izrazili n te uvrstili u drugu. Dobili bismo 63 = 2^{2k} + 2^{2k} - 2^k + (2^k - 1)^2 = 3 \cdot 2^{2k} - 3 \cdot 2^k +1, što nema rješenja jer možemo gledati jednadžbu modulo 3: svi izrazi osim zadnje jedinice djeljivi su s 3.

U drugom slučaju ponovno uvrštavmo n iz prve u drugu jednakost i dobivamo 21 = 2^{2k} + 2^{2k} - 3 \cdot 2^k + (2^k - 3)^2 = 3 \cdot 2^{2k} - 9 \cdot 2^k + 9. Rješavanjem kvadratne jednadžbe po t = 2^k dobivamo rješenja t = 4 i t = -1, odakle je 2^ k = 4, odnosno k=2, tj. m=6 i n = 1.

U trećem slučaju analogno dobivamo 9 = 2^{2k} + 2^{2k} - 7 \cdot 2^k + (2^k - 7)^2 = 3 \cdot 2^{2k} - 9 \cdot 2^k + 49, a ta jednadžba ponovno nema rješenja ako gledamo jednadžbu modulo 3.

Da bismo u potpunosti riješili zadatak, treba provjeriti i preostala 3 slučaja. U tim slučajevima nećemo dobiti nova rješenja.

Umjesto dodatnog gledanja preostala 3 slučaja, broj slučajeva mogli bismo prepoloviti. Naime, primijetimo da obje zagrade (2^k - n) i (2^{2k} + n \cdot 2^k + n^2 ) trebaju biti pozitivni brojevi (jer je druga zbroj prirodnih brojeva, a umnožak im mora biti pozitivan), te da je druga zagrada sigurno veća od druge jer vrijedi 2^{2k} + n \cdot 2^k + n^2 > n \cdot 2^k \geq 2^k > 2^k - n. Zato ne treba gledati one mogućnosti u kojima je drugi faktor u umnošku manji od prvog, tj. preostala 3 slučaja.

Upišite 1 za nastavak.