liczba nie jest pierwsza - wykaż
liczba nie jest pierwsza - wykaż
Wykaż że liczba \(\displaystyle{ F _{5} = 2 ^{32}+1}\) nie jest pierwsza. Wykorzystaj małe twierdzenie fermata.
liczba nie jest pierwsza - wykaż
\(\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.
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.
liczba nie jest pierwsza - wykaż
A jak pokazać, że jesli p jest dzielnikiem pierwszym tej liczby (tzn. \(\displaystyle{ F _{5}}\) ), to p − 1 jest krotnością 64?
- 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
liczba nie jest pierwsza - wykaż
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.
\(\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.