znaleźć najmniejszy dzielnik pierwszy
znaleźć najmniejszy dzielnik pierwszy
znaleźć najmniejszy dzielnik pierwszy liczby \(\displaystyle{ 12^{2^{15}}+1}\). Hint: jeżeli \(\displaystyle{ r}\) jest najmniejszą liczbą naturalną taką, że \(\displaystyle{ a^r \equiv 1 (\mbox{mod }p)}\) oraz \(\displaystyle{ a^k \equiv 1 (\mbox{mod }p)}\), to \(\displaystyle{ r|k}\)
- Vax
- Użytkownik
- Posty: 2913
- Rejestracja: 27 kwie 2010, o 22:07
- Płeć: Mężczyzna
- Lokalizacja: Biała Podlaska / Warszawa
- Podziękował: 4 razy
- Pomógł: 612 razy
znaleźć najmniejszy dzielnik pierwszy
Trochę odświeżę, bo zadanie ciekawe. Będziemy korzystać z tego, że \(\displaystyle{ 2^{16}+1}\) jest liczbą pierwszą. Oznaczmy przez p najmniejszy pierwszy dzielnik liczby \(\displaystyle{ 12^{2^{15}}+1}\) (oczywiście \(\displaystyle{ p\neq 2 \wedge p\neq 3}\)) oraz przyjmijmy \(\displaystyle{ t = ord_p12}\), czyli \(\displaystyle{ 12^{2^{15}} \equiv -1 \pmod{p} \wedge 12^{2^{16}} \equiv 1 \pmod{p}}\), skąd wynika \(\displaystyle{ t = 2^{16}}\), ale z twierdzenia Eulera \(\displaystyle{ 12^{p-1} \equiv 1 \pmod{p}}\) skąd \(\displaystyle{ 2^{16} | p-1}\) czyli nasze p dla pewnego całkowitego dodatniego k ma być równe \(\displaystyle{ p = 2^{16}k+1}\) Pozostaje teraz znaleźć najmniejsze takie k, że dane wyrażenie będzie pierwsze i nasza liczba będzie się przez nie dzieliła. Podstawmy najmniejszą możliwą liczbę, \(\displaystyle{ k=1}\) wtedy dostajemy liczbę pierwszą \(\displaystyle{ p = 2^{16}+1}\) pozostaje pokazać, że dane wyrażenie się przez nie dzieli:
\(\displaystyle{ 12^{2^{15}}+1 = 4^{2^{15}}\cdot 3^{2^{15}}+1 = 3^{2^{15}}\cdot 2^{2^{16}}+1}\)
Ale z twierdzenia Eulera \(\displaystyle{ 2^{2^{16}} \equiv 1 \pmod{2^{16}+1}}\) więc:
\(\displaystyle{ 3^{2^{15}}\cdot 2^{2^{16}}+1 \equiv 3^{2^{15}}+1 \pmod{2^{16}+1}}\)
Teraz zauważmy, że:
\(\displaystyle{ \left(\frac{3}{2^{16}+1}\right) = \left(\frac{2^{16}+1}{3}\right) = \left(\frac{2}{3}\right) = -1}\) czyli 3 jest nieresztą kwadratową \(\displaystyle{ \pmod{2^{16}+1}}\) więc z kryterium Eulera \(\displaystyle{ 3^{2^{15}} \equiv -1 \pmod{2^{16}+1}}\) czyli \(\displaystyle{ 3^{2^{15}}+1 \equiv 0\pmod{2^{16}+1}}\). Czyli najmniejszym dzielnikiem pierwszym liczby \(\displaystyle{ 12^{2^{15}}+1}\) jest \(\displaystyle{ 2^{16}+1}\)
\(\displaystyle{ 12^{2^{15}}+1 = 4^{2^{15}}\cdot 3^{2^{15}}+1 = 3^{2^{15}}\cdot 2^{2^{16}}+1}\)
Ale z twierdzenia Eulera \(\displaystyle{ 2^{2^{16}} \equiv 1 \pmod{2^{16}+1}}\) więc:
\(\displaystyle{ 3^{2^{15}}\cdot 2^{2^{16}}+1 \equiv 3^{2^{15}}+1 \pmod{2^{16}+1}}\)
Teraz zauważmy, że:
\(\displaystyle{ \left(\frac{3}{2^{16}+1}\right) = \left(\frac{2^{16}+1}{3}\right) = \left(\frac{2}{3}\right) = -1}\) czyli 3 jest nieresztą kwadratową \(\displaystyle{ \pmod{2^{16}+1}}\) więc z kryterium Eulera \(\displaystyle{ 3^{2^{15}} \equiv -1 \pmod{2^{16}+1}}\) czyli \(\displaystyle{ 3^{2^{15}}+1 \equiv 0\pmod{2^{16}+1}}\). Czyli najmniejszym dzielnikiem pierwszym liczby \(\displaystyle{ 12^{2^{15}}+1}\) jest \(\displaystyle{ 2^{16}+1}\)