Matematyka.pl

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}\).

Gdzie to znalazłeś? Bardzo ciekawe zadanie, chciałbym zobaczyć rozwiązanie.

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}\).

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

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ę.