Cześć
Udowodnij, że dla każdego n > 1 nieprawdą jest, że \(\displaystyle{ 2^n \equiv 1 \mod n}\)
Jak to udowodnić metodami analitycznymi?
(nie)równość modularna
-
matematyka464
- Użytkownik
- Posty: 459
- Rejestracja: 3 lis 2013, o 12:00
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 208 razy
- Pomógł: 1 raz
-
matematyka464
- Użytkownik
- Posty: 459
- Rejestracja: 3 lis 2013, o 12:00
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 208 razy
- Pomógł: 1 raz
(nie)równość modularna
Skorzystałem ale nie wiem co dalej:
\(\displaystyle{ 2^n - 1^n = kn \\ 2^{n-1} + 2^{n-2} + ... + 1 = kn}\)
\(\displaystyle{ 2^n - 1^n = kn \\ 2^{n-1} + 2^{n-2} + ... + 1 = kn}\)
-
Zahion
- Moderator
- Posty: 2095
- Rejestracja: 9 gru 2012, o 19:46
- Płeć: Mężczyzna
- Lokalizacja: Warszawa, mazowieckie
- Podziękował: 139 razy
- Pomógł: 504 razy
(nie)równość modularna
Zadanie sprowadza się do wykazania iż nie istnieje taka liczba naturalna \(\displaystyle{ n>1}\), że \(\displaystyle{ n | 2^{n} -1}\), co jest dość znanym faktem
Załóżmy przeciwnie, niech \(\displaystyle{ n}\) będzie najmniejszą liczba naturalną taką, że \(\displaystyle{ n | 2^{n} - 1}\), a \(\displaystyle{ k}\) najmniejszą liczbą naturalną taką, że \(\displaystyle{ n | 2^{k} - 1}\). Wtedy \(\displaystyle{ n > k}\), jest to przypadek szczególny z pewnego twierdzenia, które dość prosto się dowodzi rozpatrując reszty z dzielenia liczb \(\displaystyle{ 2^{0},...,2^{n}}\) przez \(\displaystyle{ n}\). Mianowicie twierdzenie mówi - dla każdej liczby nieparzystej \(\displaystyle{ n > 1}\) istnieje taka liczba naturalna \(\displaystyle{ m < n}\), że liczba \(\displaystyle{ 2^{m} - 1}\) jest podzielna przez \(\displaystyle{ n}\).
Niech \(\displaystyle{ n = km + r}\), \(\displaystyle{ 0 \le r < k}\). Mamy, że \(\displaystyle{ n | 2^{n} - 2^{km}= 2^{km}(2^{r}-1)}\), stąd \(\displaystyle{ n | 2^{r} - 1}\), bo \(\displaystyle{ n}\) jest liczbą nieparzystą. Wynika stąd, że \(\displaystyle{ r = 0}\), bo \(\displaystyle{ r < k}\). Dalej mamy, że \(\displaystyle{ k | n}\), co ciągnie za sobą podzielność \(\displaystyle{ k | 2^{k} - 1}\) i dalej wynika stąd na mocy warunku \(\displaystyle{ n > k}\) i określenia liczby \(\displaystyle{ n}\) równość \(\displaystyle{ k = 1}\), czyli \(\displaystyle{ n | 2^{1} - 1 = 1}\), co jest sprzeczne i dowodzi tezy.
Załóżmy przeciwnie, niech \(\displaystyle{ n}\) będzie najmniejszą liczba naturalną taką, że \(\displaystyle{ n | 2^{n} - 1}\), a \(\displaystyle{ k}\) najmniejszą liczbą naturalną taką, że \(\displaystyle{ n | 2^{k} - 1}\). Wtedy \(\displaystyle{ n > k}\), jest to przypadek szczególny z pewnego twierdzenia, które dość prosto się dowodzi rozpatrując reszty z dzielenia liczb \(\displaystyle{ 2^{0},...,2^{n}}\) przez \(\displaystyle{ n}\). Mianowicie twierdzenie mówi - dla każdej liczby nieparzystej \(\displaystyle{ n > 1}\) istnieje taka liczba naturalna \(\displaystyle{ m < n}\), że liczba \(\displaystyle{ 2^{m} - 1}\) jest podzielna przez \(\displaystyle{ n}\).
Niech \(\displaystyle{ n = km + r}\), \(\displaystyle{ 0 \le r < k}\). Mamy, że \(\displaystyle{ n | 2^{n} - 2^{km}= 2^{km}(2^{r}-1)}\), stąd \(\displaystyle{ n | 2^{r} - 1}\), bo \(\displaystyle{ n}\) jest liczbą nieparzystą. Wynika stąd, że \(\displaystyle{ r = 0}\), bo \(\displaystyle{ r < k}\). Dalej mamy, że \(\displaystyle{ k | n}\), co ciągnie za sobą podzielność \(\displaystyle{ k | 2^{k} - 1}\) i dalej wynika stąd na mocy warunku \(\displaystyle{ n > k}\) i określenia liczby \(\displaystyle{ n}\) równość \(\displaystyle{ k = 1}\), czyli \(\displaystyle{ n | 2^{1} - 1 = 1}\), co jest sprzeczne i dowodzi tezy.