szukanie zaawansowane
 [ Posty: 5 ] 
Autor Wiadomość
Mężczyzna Offline
 Tytuł: Dowód z modulo
PostNapisane: 23 lis 2015, o 17:20 
Użytkownik

Posty: 176
Lokalizacja: Polska
Udowodnij, że

\[2^{n}\neq 1(mod\, \, \, \, n)\]

dla każdego n>1
Uniwersytet Wrocławski Instytut Matematyczny - rekrutacja 2018
Góra
Mężczyzna Offline
 Tytuł: Dowód z modulo
PostNapisane: 23 lis 2015, o 17:51 
Moderator

Posty: 1963
Lokalizacja: Trzebiatów
379094.htm#p5302948
Góra
Mężczyzna Offline
 Tytuł: Dowód z modulo
PostNapisane: 23 lis 2015, o 17:56 
Użytkownik

Posty: 9836
Lokalizacja: Bydgoszcz
Inaczej niż w linku:

Załóżmy, że dla pewnego n przystawanie zachodzi. Niech p będzie najmniejszą liczbą pierwszą dzielącą n (oczywiście p>2). Z Małego Twierdzenia Fermata mamy:
2^{p-1}\equiv 1 \pmod p
oraz oczywiście
2^{n}\equiv 1 \pmod p
Ale n i p-1 są względnie pierwsze, bo n nie ma dzielników mniejszych niż p i większych od jeden. Tak więc istnieją takie całkowite k,l, że:
kn+l(p-1)=1
W takim razie:
2^1\equiv 2^{kn+l(p-1)} = (2^n)^k\cdot (2^{p-1})^l\equiv 1^k \cdot 1^l =1 \pmod p
co oznacza sprzeczność.

Q.
Góra
Mężczyzna Offline
 Tytuł: Dowód z modulo
PostNapisane: 23 lis 2015, o 18:39 
Użytkownik

Posty: 14748
Lokalizacja: Bydgoszcz
Ostrożnie:
Cytuj:
2^1\equiv 2^{kn+l(p-1)} =\red  (2^n)^k\cdot (2^{p-1})^l\equiv 1^k \cdot 1^l \black=1 \pmod p


Co oznacza to przystawanie gdy k=-5?
Góra
Mężczyzna Offline
 Tytuł: Dowód z modulo
PostNapisane: 23 lis 2015, o 18:42 
Użytkownik

Posty: 9836
Lokalizacja: Bydgoszcz
Jeśli m>0, to przez a^{-m} rozumiemy (a^{-1})^m, a przez a^{-1} taką liczbę b dla której ab\equiv 1\pmod p (zawsze istnieje, bo p pierwsze).

Q.
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 5 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Własności synchronicznych szyfrów strumieniowych dowód  Sabisia193  0
 Zasada Dirichleta - dowód.  psimon  3
 Dwumian Newtona - dowód kombinatoryczny  patry93  1
 dowod permutacji  piotrs67  2
 Dowód, dwumian Newtona  withdrawn  1
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl