Dowód z modulo

[jackblack]

Udowodnij, że

\(\displaystyle{ \[2^{n}\neq 1(mod\, \, \, \, n)\]}\)

dla każdego \(\displaystyle{ n>1}\)

[Zahion]

379094.htm#p5302948

[Qń]

Inaczej niż w linku:

Załóżmy, że dla pewnego \(\displaystyle{ n}\) przystawanie zachodzi. Niech \(\displaystyle{ p}\) będzie najmniejszą liczbą pierwszą dzielącą \(\displaystyle{ n}\) (oczywiście \(\displaystyle{ p>2}\)). Z Małego Twierdzenia Fermata mamy:
\(\displaystyle{ 2^{p-1}\equiv 1 \pmod p}\)
oraz oczywiście
\(\displaystyle{ 2^{n}\equiv 1 \pmod p}\)
Ale \(\displaystyle{ n}\) i \(\displaystyle{ p-1}\) są względnie pierwsze, bo \(\displaystyle{ n}\) nie ma dzielników mniejszych niż \(\displaystyle{ p}\) i większych od jeden. Tak więc istnieją takie całkowite \(\displaystyle{ k,l}\), że:
\(\displaystyle{ kn+l(p-1)=1}\)
W takim razie:
\(\displaystyle{ 2^1\equiv 2^{kn+l(p-1)} = (2^n)^k\cdot (2^{p-1})^l\equiv 1^k \cdot 1^l =1 \pmod p}\)
co oznacza sprzeczność.

Q.

[a4karo]

Ostrożnie:

\(\displaystyle{ 2^1\equiv 2^{kn+l(p-1)} =\red (2^n)^k\cdot (2^{p-1})^l\equiv 1^k \cdot 1^l \black=1 \pmod p}\)

Co oznacza to przystawanie gdy \(\displaystyle{ k=-5}\)?

[Qń]

Jeśli \(\displaystyle{ m>0}\), to przez \(\displaystyle{ a^{-m}}\) rozumiemy \(\displaystyle{ (a^{-1})^m}\), a przez \(\displaystyle{ a^{-1}}\) taką liczbę \(\displaystyle{ b}\) dla której \(\displaystyle{ ab\equiv 1\pmod p}\) (zawsze istnieje, bo \(\displaystyle{ p}\) pierwsze).

Q.