Małe Twierdzenie Fermata - 2 zadanka
-
- Użytkownik
- Posty: 48
- Rejestracja: 5 gru 2007, o 12:29
- Płeć: Mężczyzna
- Lokalizacja: Toruń
- Podziękował: 12 razy
- Pomógł: 3 razy
Małe Twierdzenie Fermata - 2 zadanka
1)Wiadomo, ze liczba pierwsza p dzieli liczbę 111...11 gdzie 1 wystepuje p razy. Udowodnij ze p=3.
2) Niech a i b beda liczbami naturalnymi, p - zas liczba pierwsza. Udowodnij, ze jezeli liczba
a^p - b^p jest podzielna przez p jest podzielna rowniez przez p^2.
Zadanie z kolko matematycznego dla olimpijczykow H.Pawlowskiego, mam z nimi problem, wiec jesli ktos ma chwilke to prosze o rozwiazanie
2) Niech a i b beda liczbami naturalnymi, p - zas liczba pierwsza. Udowodnij, ze jezeli liczba
a^p - b^p jest podzielna przez p jest podzielna rowniez przez p^2.
Zadanie z kolko matematycznego dla olimpijczykow H.Pawlowskiego, mam z nimi problem, wiec jesli ktos ma chwilke to prosze o rozwiazanie
-
- Użytkownik
- Posty: 2234
- Rejestracja: 26 paź 2006, o 18:08
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 22 razy
- Pomógł: 390 razy
Małe Twierdzenie Fermata - 2 zadanka
1)Zauważ, że \(\displaystyle{ p|11...1=10^{p-1}+10^{p-2}+...+10+1}\)
Załóżmy, że p nie dzieli 9. Zatem nasza podzielność będzie równoważna:
\(\displaystyle{ p|(10^{p-1}+10^{p-2}+...+10+1)*9=(10^{p-1}+10^{p-2}+...+10+1)*(10-1)=10^{p}-1}\)
Ale z małego twierdzenia Fermata:
\(\displaystyle{ 10^{p}-1\equiv 10-1\equiv 9 \ (modp)}\)
A z tego otrzymujemy, że \(\displaystyle{ p|9}\) co jest sprzeczne z założeniem, co ostatecznie daje nam \(\displaystyle{ p=3}\)
2)Podpowiedź:
\(\displaystyle{ (p|(a^{p}-b^{p}))\Rightarrow (p|(a-b))}\)
Załóżmy, że p nie dzieli 9. Zatem nasza podzielność będzie równoważna:
\(\displaystyle{ p|(10^{p-1}+10^{p-2}+...+10+1)*9=(10^{p-1}+10^{p-2}+...+10+1)*(10-1)=10^{p}-1}\)
Ale z małego twierdzenia Fermata:
\(\displaystyle{ 10^{p}-1\equiv 10-1\equiv 9 \ (modp)}\)
A z tego otrzymujemy, że \(\displaystyle{ p|9}\) co jest sprzeczne z założeniem, co ostatecznie daje nam \(\displaystyle{ p=3}\)
2)Podpowiedź:
\(\displaystyle{ (p|(a^{p}-b^{p}))\Rightarrow (p|(a-b))}\)
-
- Użytkownik
- Posty: 48
- Rejestracja: 5 gru 2007, o 12:29
- Płeć: Mężczyzna
- Lokalizacja: Toruń
- Podziękował: 12 razy
- Pomógł: 3 razy
Małe Twierdzenie Fermata - 2 zadanka
Dziekuje bardzo za szybka odpowiedz, o ile pierwsze widze - bardzo ladne rozwiazanie
nie wiem skad wynika podpowiedz do zadania drugiego do konca ? wiem tylko ze wiele mi ona ulatwia
nie wiem skad wynika podpowiedz do zadania drugiego do konca ? wiem tylko ze wiele mi ona ulatwia
-
- Użytkownik
- Posty: 2234
- Rejestracja: 26 paź 2006, o 18:08
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 22 razy
- Pomógł: 390 razy
Małe Twierdzenie Fermata - 2 zadanka
Skoro \(\displaystyle{ a^{p}-b^{p}\equiv 0 \ (modp)}\)
Oraz z MTF:
\(\displaystyle{ (a^{p}\equiv a \ (modp)) (b^{p}\equiv b \ (modp))}\)
to \(\displaystyle{ a^{p}-b^{p}\equiv a-b\equiv 0 \ (modp)}\)
Oraz z MTF:
\(\displaystyle{ (a^{p}\equiv a \ (modp)) (b^{p}\equiv b \ (modp))}\)
to \(\displaystyle{ a^{p}-b^{p}\equiv a-b\equiv 0 \ (modp)}\)
-
- Użytkownik
- Posty: 1251
- Rejestracja: 30 sty 2007, o 20:22
- Płeć: Mężczyzna
- Lokalizacja: Koziegłówki/Wrocław
- Podziękował: 352 razy
- Pomógł: 33 razy
Małe Twierdzenie Fermata - 2 zadanka
Odkopię troszkę.
Przy okazji - czy takie alternatywne rozwiązanie jest poprawne:
zakładamy, że p nie dzieli 9 i z MTF: \(\displaystyle{ p| 10^p -10 = (10^p -1) -9 \Rightarrow p \nmid 10^p -1}\), czyli \(\displaystyle{ \frac{11 \ldots 1}{p} \notin \mathbb{Z}}\) - sprzeczność, która kończy dowód.
Co do zadania drugiego - nie widzę niestety jak można by to ruszyć dalej, bo samo \(\displaystyle{ p|a-b}\) z pewnością nie wystarcza.
Czy to aby nie blef? Wydaje mi się, że winno być: \(\displaystyle{ 10^{p-1} - 1}\) albo \(\displaystyle{ 10^{p}-10}\)...\(\displaystyle{ 10^{p}-1\equiv 10-1\equiv 9 \ (modp)}\)
Przy okazji - czy takie alternatywne rozwiązanie jest poprawne:
zakładamy, że p nie dzieli 9 i z MTF: \(\displaystyle{ p| 10^p -10 = (10^p -1) -9 \Rightarrow p \nmid 10^p -1}\), czyli \(\displaystyle{ \frac{11 \ldots 1}{p} \notin \mathbb{Z}}\) - sprzeczność, która kończy dowód.
Co do zadania drugiego - nie widzę niestety jak można by to ruszyć dalej, bo samo \(\displaystyle{ p|a-b}\) z pewnością nie wystarcza.
- smigol
- Użytkownik
- Posty: 3454
- Rejestracja: 20 paź 2007, o 23:10
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 89 razy
- Pomógł: 353 razy
Małe Twierdzenie Fermata - 2 zadanka
Skoro p jest liczbą pierwszą, zaś a całkowitą (nasza dziesiątka) to:\(\displaystyle{ a^p \equiv a \ (mod \ p)}\)
w drugim wzór skróconego mnożenia.
w drugim wzór skróconego mnożenia.
-
- Użytkownik
- Posty: 1251
- Rejestracja: 30 sty 2007, o 20:22
- Płeć: Mężczyzna
- Lokalizacja: Koziegłówki/Wrocław
- Podziękował: 352 razy
- Pomógł: 33 razy
Małe Twierdzenie Fermata - 2 zadanka
smigol - heh, teraz zdałem sobie sprawę, że to jest "przekształcone" już MTF (i w sumie to samo, co u mnie), więc faktycznie wszystko gra - przepraszam
Domyślam się, że masz na myśli to: \(\displaystyle{ a^p-b^p=(a-b)(a^{p-1}+ a^{p-2}b + \ldots + ab^{p-2} + b^{p-1} )}\), więc pozostaje wykazać podzielność drugiego czynnika przez p, czego jednak nie widzę.
Domyślam się, że masz na myśli to: \(\displaystyle{ a^p-b^p=(a-b)(a^{p-1}+ a^{p-2}b + \ldots + ab^{p-2} + b^{p-1} )}\), więc pozostaje wykazać podzielność drugiego czynnika przez p, czego jednak nie widzę.
Ostatnio zmieniony 27 sty 2010, o 20:54 przez patry93, łącznie zmieniany 1 raz.
- smigol
- Użytkownik
- Posty: 3454
- Rejestracja: 20 paź 2007, o 23:10
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 89 razy
- Pomógł: 353 razy
Małe Twierdzenie Fermata - 2 zadanka
Np.
\(\displaystyle{ a^{p-2}b \equiv a^{p-1} \ (mod \ p)}\)
(dlaczego?)
Podobnie z pozostałymi składnikami sumy z drugiego nawiasu.
\(\displaystyle{ a^{p-2}b \equiv a^{p-1} \ (mod \ p)}\)
(dlaczego?)
Podobnie z pozostałymi składnikami sumy z drugiego nawiasu.