Dowód niepodzielności
- xxDorianxx
- Użytkownik
- Posty: 413
- Rejestracja: 1 paź 2016, o 17:06
- Płeć: Mężczyzna
- Lokalizacja: Rybnik
- Podziękował: 88 razy
- Pomógł: 22 razy
Dowód niepodzielności
Witam mam problem z tym zadaniem.Wykaż,że nie ma takiego \(\displaystyle{ n>1}\) dzielącego \(\displaystyle{ 2^n-1}\).
- Premislav
- Użytkownik
- Posty: 15687
- Rejestracja: 17 sie 2012, o 13:12
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 196 razy
- Pomógł: 5221 razy
Re: Dowód niepodzielności
Jeżeli \(\displaystyle{ n}\) jest parzyste, to nawet \(\displaystyle{ 2\nmid 2^n-1}\), tym bardziej \(\displaystyle{ n\nmid 2^n-1}\).
Dalej przypuśćmy nie wprost, że \(\displaystyle{ n}\) jest liczbą nieparzystą taką, że \(\displaystyle{ n|2^n-1}\).
Niech \(\displaystyle{ p}\) będzie najmniejszą liczbą pierwszą dzielącą \(\displaystyle{ n}\). Wówczas w szczególności \(\displaystyle{ p|2^n-1}\). Z małego twierdzenia Fermata mamy \(\displaystyle{ 2^{p-1}\equiv 1\pmod{p}}\).
Niech teraz \(\displaystyle{ r}\) będzie rzędem \(\displaystyle{ 2}\) modulo \(\displaystyle{ p}\), tj. \(\displaystyle{ r}\) jest najmniejszą liczbą całkowitą dodatnią, która spełnia zależność \(\displaystyle{ 2^r\equiv 1\pmod{p}}\)
Udowodnijmy przez sprzeczność, że \(\displaystyle{ r|n}\) (zostawiam ten fragment jako proste ćwiczenie dla Ciebie). Ponieważ \(\displaystyle{ r\le p-1}\), to albo \(\displaystyle{ r=1}\) (łatwo sprawdzamy, że to prowadzi do sprzeczności), albo istnieje liczba pierwsza \(\displaystyle{ q\le p-1}\), która dzieli \(\displaystyle{ r}\). Wówczas z przechodniości relacji podzielności także \(\displaystyle{ q|n}\), ale \(\displaystyle{ q<p}\), sprzeczność z minimalnością \(\displaystyle{ p}\).
Dalej przypuśćmy nie wprost, że \(\displaystyle{ n}\) jest liczbą nieparzystą taką, że \(\displaystyle{ n|2^n-1}\).
Niech \(\displaystyle{ p}\) będzie najmniejszą liczbą pierwszą dzielącą \(\displaystyle{ n}\). Wówczas w szczególności \(\displaystyle{ p|2^n-1}\). Z małego twierdzenia Fermata mamy \(\displaystyle{ 2^{p-1}\equiv 1\pmod{p}}\).
Niech teraz \(\displaystyle{ r}\) będzie rzędem \(\displaystyle{ 2}\) modulo \(\displaystyle{ p}\), tj. \(\displaystyle{ r}\) jest najmniejszą liczbą całkowitą dodatnią, która spełnia zależność \(\displaystyle{ 2^r\equiv 1\pmod{p}}\)
Udowodnijmy przez sprzeczność, że \(\displaystyle{ r|n}\) (zostawiam ten fragment jako proste ćwiczenie dla Ciebie). Ponieważ \(\displaystyle{ r\le p-1}\), to albo \(\displaystyle{ r=1}\) (łatwo sprawdzamy, że to prowadzi do sprzeczności), albo istnieje liczba pierwsza \(\displaystyle{ q\le p-1}\), która dzieli \(\displaystyle{ r}\). Wówczas z przechodniości relacji podzielności także \(\displaystyle{ q|n}\), ale \(\displaystyle{ q<p}\), sprzeczność z minimalnością \(\displaystyle{ p}\).
- xxDorianxx
- Użytkownik
- Posty: 413
- Rejestracja: 1 paź 2016, o 17:06
- Płeć: Mężczyzna
- Lokalizacja: Rybnik
- Podziękował: 88 razy
- Pomógł: 22 razy