pokazać, że nwd > 1

[matinf]

Witam,

Niech \(\displaystyle{ n > 0}\)
\(\displaystyle{ J(4) = 1111 \\ J(3) = 111 \\ J(6) = 111111}\)
Widać, jak zdefiniowana jest ta liczba - ilość jedynek (tzn w zapisie dziesiętnym).

Pokazać, że jeśli liczba pierwsza \(\displaystyle{ p}\) dzieli \(\displaystyle{ J(n)}\) to wówczas \(\displaystyle{ NWD(p - 1, n) > 1}\)

[Hydra147]

Hmm, dla \(\displaystyle{ n=p=3}\) mamy kontrprzykład.

[matinf]

zapomniałem dodać warunek, że \(\displaystyle{ p>3}\)

[Qń]

Oczywiście \(\displaystyle{ J(n)= \frac{10^n-1}{9}}\), jeśli więc \(\displaystyle{ p>3}\) dzieli \(\displaystyle{ J(n)}\), to także \(\displaystyle{ p|(10^n-1)}\), czyli:
\(\displaystyle{ 10^n\equiv 1 \pmod{p}}\)
Z małego twierdzenia Fermata wiemy też, że:
\(\displaystyle{ 10^{p-1}\equiv 1\pmod{p}}\)

Gdyby było wbrew tezie \(\displaystyle{ NWD(p-1,n)=1}\), to z rozszerzonego algorytmu Euklidesa wiemy, że dla pewnych \(\displaystyle{ k,l}\) całkowitych byłoby \(\displaystyle{ 1=kn+l(p-1)}\) i wtedy:
\(\displaystyle{ 10= 10^1= 10^{kn+l(p-1)}=(10^n)^k\cdot (10^{p-1})^l \equiv 1^k\cdot 1^l=1 \pmod p}\)
co jest ewidentną sprzecznością.

Q.

[matinf]

Tutaj, ta sprzeczność polegała na tym, że 10 przystaje do jeden, mod liczba pierwsza ?

Bo ta kongruencja nie zajdzie nigdy, tzn nigdy 10 nie da reszty jeden z dzielenia przez liczbę pierwszą.

I to jest ta sprzeczność ?

[Qń]

No przecież
\(\displaystyle{ 10\equiv 1\pmod{p}}\)
oznacza z definicji, że \(\displaystyle{ p|(10-1)}\) co jest niemożliwe.

Q.