znaleźć najmniejszy dzielnik pierwszy

Podzielność. Reszty z dzielenia. Kongruencje. Systemy pozycyjne. Równania diofantyczne. Liczby pierwsze i względnie pierwsze. NWW i NWD.
kade
Użytkownik
Użytkownik
Posty: 11
Rejestracja: 19 gru 2010, o 22:28
Płeć: Mężczyzna
Lokalizacja: PL

znaleźć najmniejszy dzielnik pierwszy

Post autor: kade »

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}\)
Awatar użytkownika
Vax
Użytkownik
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

Post autor: Vax »

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}\)
ODPOWIEDZ