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

Posty: 176
Lokalizacja: Polska
Udowodnij, że

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

dla każdego n>1
Góra
Mężczyzna Offline
 Tytuł: Dowód z modulo
PostNapisane: 23 lis 2015, o 16:51 
Moderator

Posty: 2043
Lokalizacja: Trzebiatów
379094.htm#p5302948
Góra
Mężczyzna Offline
 Tytuł: Dowód z modulo
PostNapisane: 23 lis 2015, o 16: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 17:39 
Użytkownik

Posty: 15823
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 17: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 
 Tożsamość Eulera - dowód  Siwy1991  2
 Symbol newtona - dowód własności  ziurek  2
 dowód indukcyjny - zadanie 50  tukanik  3
 Wielomian dowód  Tweester  1
 pomalowana płaszczyzna dowód pytanie  wielkireturner  6
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl