Viikkotehtävä: tulon tekijä (viikko 10/2019)

lukuteoria

#1

Viikkotehtävä

Vastausaikaa su 10.3.2019 klo 24 asti
Vastausaika on päättynyt. Voit keskustella tehtävästä ja sen ratkaisuideoista vapaasti tässä ketjussa.

Tehtävä

Etsi kaikki alkuluvut p ja q, joille tulo pq jakaa tulon (5^p-2^p)(5^q-2^q).

Vihje

Bézout’n identiteetistä seuraa, että jos \textrm{syt}(a,m)=\textrm{syt}(b,m)=1, a^x \equiv b^x \pmod{m} ja a^y\equiv b^y\pmod{m}, niin

a^{\textrm{syt}(x,y)} \equiv b^{\textrm{syt}(x,y)} \pmod{m}

Yritä hyödyntää tätä etsiessäsi tulosta, joka sulkee useimmat p:n ja q:n arvot pois.


sulki #2

avasi #3

#4

Tutkitaan ensin tapaus p, q > 5.

Fermat’n pienen lauseen nojalla 5^p - 2^p \equiv 5 - 2 \equiv 3 \not\equiv 0 \pmod{p}. Siis jos pq jakaa tulon (5^p - 2^p)(5^q - 2^q), niin p jakaa luvun 5^q - 2^q.

Toisaalta p jakaa myös luvun 5^{p-1} - 2^{p-1}. Olkoon d = \gcd(p-1, q). Vinkin nojalla (tai blogipostauksen nojalla) pätee

5^d \equiv 2^d \pmod{p}

Selvästi d \neq 1, joten d = q. Täten q \mid p-1. Vastaavaa päättelyä voisi kuitenkin soveltaa myös q:lle p:n sijasta, joten p \mid q-1. Tämä on selvästi mahdotonta. Siis joko p \le 5 tai q \le 5 kaikilla ratkaisuilla (p, q). Loppu on helppo rutiinitarkastus.