Juuren ottaminen moduloissa

Tässä postauksessa käsitellään miten muotoa $a^n \equiv b^n \pmod{m}$ olevasta yhtälöstä voi ottaa juuren tietyin ehdoin.

Lemma (juuren ottaminen)

Olkoon $a^n \equiv b^n \pmod{m}$ sekä $a^k \equiv b^k \pmod{m}$, missä $a, b, k, n \in \mathbb{Z}$, ja $\syt(a, m) = \syt(b, m) = 1$. Nyt pätee

Todistus

Olkoon $d = \syt(n, k)$. Bezout’n lemman nojalla $d$ voidaan kirjoittaa muodossa $xn + yk$, missä $x, y \in \mathbb{Z}$. Korottamalla yhtälön $a^n \equiv b^n \pmod{m}$ potenssiin $x$, yhtälön $a^k \equiv b^k \pmod{m}$ potenssiin $y$, ja kertomalla yhtälöt keskenään saamme halutun väitteen.

Huomautus

Jotta negatiiviset eksponentit ovat määritelty, tulee ehdon $\syt(a, m) = \syt(b, m) = 1$ päteä.

Korollaari

Olkoon $a^n \equiv b^n \pmod{m}$, missä $\syt(a, m) = \syt(b, m) = 1$. Pätee

Erityisesti, jos $\syt(n, \phi(m)) = 1$, pätee $a \equiv b \pmod{m}$.

Lemma ja korollaari voivat usein olla hyödyllisiä myös iinä tapauksessa kun $b = 1$, eli tutkittaessa yhtälöä $a^n \equiv 1 \pmod{m}$

Huomautus

Korollaarista voi esittää myös vahvemman version korvaamalla $\phi(m)$:n Carmichaelin lambda-funktiolla $m$:stä.

Esimerkkitehtävä (IMO, 1999, T4)

Määritä kaikki positiivisten kokonaislukujen parit $(p, n)$, joilla pätee ehdot

$p$ on alkuluku

$n \le 2p$

$n^{p-1} \mid (p-1)^n + 1$

Ratkaisu

$n = 1$ on ratkaisu kaikille $p$. Oletetaan $n > 1$.

Jos $p = 2$, niin $n = 1$ tai $n = 2$. Oletetaan $p > 2$.

Selvästi $n$ on pariton, ja $\syt(p-1, n) = 1$. Olkoon $q$ luvun $n$ pienin alkutekijä. Pätee $(p-1)^n \equiv -1 \pmod{q}$, joten

Fermat’n pienen lauseen nojalla pätee (ottaen huomioon $\syt(p-1, q) = 1$)

Sillä $q$ on luvun $n$ pienin alkutekijä, on $\syt(q-1, n) = 1$, joten $\syt(q-1, 2n) = 2$. Lemman nojalla pätee

Tämä tarkoittaa, että $q \mid p(p-2)$.

Jos $q \mid p-2$, saamme aikaan ristiriidan: aiemmin totesimme $(p-1)^n \equiv -1 \pmod{q}$. Tällöin olisi $1 \equiv -1 \pmod{q}$, mikä on mahdotonta luvun $n$ ollessa pariton.

Täten $q \mid p$. Siispä $q = p$, ja $q \mid n$, joten $n = p$ tai $n = 2p$. Sillä $n$ on pariton, on $n = p$.

Enää tulee siis ratkaista, milloin $p^{p-1} \mid (p-1)^p + 1$. Tämä onnistuu helposti LTE:n avulla:

$v_p((p-1)^p + 1) = v_p((p-1)^p - (-1)^p) = v_p(p-1 - (-1)) + v_p(p) = 2$. Siis tulee olla $p - 1 \le 2$, joten $p \le 3$. Tästä saamme ratkaisun: $p = n = 3$.

Huomautus Idea siitä, että tutkitaan jonkin luvun pienintä alkutekijää ei ole äärimmäisen harvinainen.

Esimerkkitehtävä (Anne-Maria Ernvall-Hytösen lukuteoriamoniste, IMO-valintaleiri, 2018)

Osoita, että yhtälöllä

$\lbrace x^3 \rbrace + \lbrace y^3 \rbrace = \lbrace z^3 \rbrace $

on äärettömän monta ratkaisua $(x, y, z)$, missä $x, y, z$ ovat rationaalisia mutteivat kokonaislukuja. Tässä $\lbrace r \rbrace$ tarkoittaa luvun $r$ murto-osaa.

Ratkaisu

Valitaan $x = \frac{a}{5}$, $y = \frac{b}{5}$, $z = \frac{c}{5}$. Tehtävä palautuu siihen, että haluamme löytää kokonaisluvut $a, b, c$, joilla

ja $5 \nmid abc$, ja lukujen $a^3$, $b^3$ jakojäännösten summa jaettaessa luvulla $5^3$ on pienempi kuin luvun $c^3$ jakojäännös.

Sillä $\syt(3, \phi(5^3)) = \syt(3, 100) = 1$, on funktio $f(x) = (x^3 \pmod{5^3})$, $f : A \to A$ injektiivinen, missä $A$ on kaikkien lukujen $a$ joukko, joilla $5 \nmid a$, $0 \le a < 5^3$. Funktio äärelliseltä joukolta itselleen on selvästi injektiivinen joss se on surjektio (miksi?).

Täten on olemassa jotkin $a, b, c$, joilla $a^3 \equiv 1 \pmod{5^3}$, $b^3 \equiv 2 \pmod{5^3}$ ja $c^3 \equiv 3 \pmod{5^3}$. Lisäksi nämä ehdot toteuttavia lukuja on äärettömän monta. Olemme näin ollen todistaneet, että tehtävänannon yhtälöllä on äärettömän monta ratkaisua.

Harjoitustehtäviä

Määritä kaikki $n \in N$ joilla $n \mid 2^n - 1$

(Kiina 1999, kansallisen kilpailun finaali, tehtävä 4)

Olkoon $m$ positiivinen kokonaisluku. Osoita, että on olemassa kokonaisluvut $a, b, k$ niin, että $a$ ja $b$ ovat parittomia, $k \ge 0$, ja

(Baltian tie 2005, T16)

Olkoon $p$ alkuluku ja $n$ positiivinen kokonaisluku. Olkoon $q$ luvun $(n+1)^p - n^p$ positiivinen tekijä. Osoita, että $q-1$ on jaollinen luvulla $p$.

(Baltian tie 2008, T9)

Positiiviset kokonaisluvut $a$ ja $b$ toteuttavat yhtälön

Osoita, että $a$ ja $b$ ovat kongruentteja keskenään modulo $1008$.