liczba nie jest pierwsza - wykaż

Podzielność. Reszty z dzielenia. Kongruencje. Systemy pozycyjne. Równania diofantyczne. Liczby pierwsze i względnie pierwsze. NWW i NWD.
21mat
Użytkownik
Użytkownik
Posty: 319
Rejestracja: 23 mar 2011, o 09:58
Płeć: Mężczyzna

liczba nie jest pierwsza - wykaż

Post autor: 21mat »

Wykaż że liczba \(\displaystyle{ F _{5} = 2 ^{32}+1}\) nie jest pierwsza. Wykorzystaj małe twierdzenie fermata.
szw1710

liczba nie jest pierwsza - wykaż

Post autor: szw1710 »

\(\displaystyle{ F(5) = 2^{32} + 1 = 4\,294\,967\,297 = 641\cdot 6\,700\,417}\)

W którejś z książek popularyzatorskich to wyczytałem. Nie miej mnie za geniusza od rachunków.

Ale dla ciekawości właśnie zapuściłem Maximę: \(\displaystyle{ \text{factor}(2^{32}+1)}\) Podaje ten rozkład.
21mat
Użytkownik
Użytkownik
Posty: 319
Rejestracja: 23 mar 2011, o 09:58
Płeć: Mężczyzna

liczba nie jest pierwsza - wykaż

Post autor: 21mat »

A jak pokazać, że jesli p jest dzielnikiem pierwszym tej liczby (tzn. \(\displaystyle{ F _{5}}\) ), to p − 1 jest krotnością 64?
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

liczba nie jest pierwsza - wykaż

Post autor: Vax »

Pokażemy więcej, a dokładnie, że dla każdego dzielnika pierwszego p liczby \(\displaystyle{ F_n}\) zachodzi \(\displaystyle{ 2^{n+1} | p-1}\), niech p będzie dowolnym dzielnikiem pierwszym liczby \(\displaystyle{ F_n}\) (oczywiście \(\displaystyle{ p \neq 2}\)), wówczas:

\(\displaystyle{ 2^{2^n} \equiv -1\pmod{p} \Rightarrow 2^{2^{n+1}} \equiv 1\pmod{p}}\)

Niech \(\displaystyle{ t = ord_p 2}\), otrzymujemy wówczas:

\(\displaystyle{ t \nmid 2^n \wedge t \mid 2^{n+1} \Leftrightarrow t = 2^{n+1}}\)

Ale z mtf mamy również \(\displaystyle{ t | p-1 \Leftrightarrow 2^{n+1} | p-1}\) qed.
ODPOWIEDZ