Teoria liczb - liczba z n jedynkami
- acmilan
- Użytkownik
- Posty: 402
- Rejestracja: 27 kwie 2009, o 15:29
- Płeć: Mężczyzna
- Lokalizacja: Warszawa-Praga
- Podziękował: 40 razy
- Pomógł: 50 razy
Teoria liczb - liczba z n jedynkami
Niech \(\displaystyle{ f(n)}\) oznacza liczbę złożoną z \(\displaystyle{ n}\) jedynek (w zapisie dziesiętnym). Udowodnij, że jeśli liczba pierwsza \(\displaystyle{ p>3}\) jest dzielnikiem \(\displaystyle{ f(n)}\), to \(\displaystyle{ NWD(n,p-1)>1}\).
- Zordon
- Użytkownik
- Posty: 4977
- Rejestracja: 12 lut 2008, o 21:42
- Płeć: Mężczyzna
- Lokalizacja: Kraków
- Podziękował: 75 razy
- Pomógł: 910 razy
Teoria liczb - liczba z n jedynkami
Można założyć, że \(\displaystyle{ p>5}\)
\(\displaystyle{ p|f(n)}\) więc \(\displaystyle{ p|9f(n)=10^n-1}\), innymi słowy:
\(\displaystyle{ 10^n\equiv 1 \pmod{p}}\)
Niech \(\displaystyle{ d}\) to rząd elementu \(\displaystyle{ 10}\) w grupie \(\displaystyle{ \ZZ_p^*}\). Wtedy \(\displaystyle{ d|(p-1)}\) oraz \(\displaystyle{ d|n}\). Łatwo też widać, że \(\displaystyle{ d>1}\).
\(\displaystyle{ p|f(n)}\) więc \(\displaystyle{ p|9f(n)=10^n-1}\), innymi słowy:
\(\displaystyle{ 10^n\equiv 1 \pmod{p}}\)
Niech \(\displaystyle{ d}\) to rząd elementu \(\displaystyle{ 10}\) w grupie \(\displaystyle{ \ZZ_p^*}\). Wtedy \(\displaystyle{ d|(p-1)}\) oraz \(\displaystyle{ d|n}\). Łatwo też widać, że \(\displaystyle{ d>1}\).
- acmilan
- Użytkownik
- Posty: 402
- Rejestracja: 27 kwie 2009, o 15:29
- Płeć: Mężczyzna
- Lokalizacja: Warszawa-Praga
- Podziękował: 40 razy
- Pomógł: 50 razy
Teoria liczb - liczba z n jedynkami
Zordon - dzięki, znalazłem rozwiązanie bez odwoływania się do teorii grup (tylko że po angielsku):
... of-1s?rq=1
robertm19 - zadanie wziąłem z kolokwium z matematyki dyskretnej na UW
... of-1s?rq=1
robertm19 - zadanie wziąłem z kolokwium z matematyki dyskretnej na UW
- Zordon
- Użytkownik
- Posty: 4977
- Rejestracja: 12 lut 2008, o 21:42
- Płeć: Mężczyzna
- Lokalizacja: Kraków
- Podziękował: 75 razy
- Pomógł: 910 razy
Teoria liczb - liczba z n jedynkami
To jest to samo, tylko ubrane w elementarną nomenklaturę. Moim zdaniem dowód odwołujący się do grupy \(\displaystyle{ \ZZ_p^*}\) daje szersze spojrzenie na sytuację.