Małe twierdzenie Fermata, postać skrócona

[gszpetkowski]

Na wstępnie chciałbym zaznaczyć, że bardziej jestem programistą niż matematykiem i mogę coś przeinaczać. W do liczb pierwszych natrafiłem na małe twierdzenie Fermata w postaci:

\(\displaystyle{ a^{n}\equiv a \pmod{n}}\) (3.2)

Twierdzenie zostało przedstawione w postaci, że jeżeli \(\displaystyle{ n}\) jest liczbą pierwszą, to dla każdego całkowitego \(\displaystyle{ a}\) zachodzi relacja przystawania modulo (ang. congruence) dla liczb \(\displaystyle{ a^{n}}\) oraz \(\displaystyle{ a}\) względem \(\displaystyle{ n}\). Innymi słowy zachodzi \(\displaystyle{ n \mid a^{n} - a}\). Nie zgłębiając w dowód trafiłem następnie na alternatywną postać, mianowicie:

\(\displaystyle{ a^{n-1}\equiv 1 \pmod{n}}\) (3.3)

W wolnym tłumaczeniu zostało to opatrzone komentarzem, że gdy \(\displaystyle{ a}\) is względnie pierwsze (ang. coprime) z \(\displaystyle{ n}\), to możliwe jest podzielenie obydwu stron (3.2). Postać (3.3) zachodzi w sytuacji gdy \(\displaystyle{ n}\) jest liczbą pierwszą i \(\displaystyle{ n}\) nie dzieli \(\displaystyle{ a}\).

Nie jestem natomiast pewien w jaki sposób można przejść z postaci (3.2) do (3.3) i czy poniższy sposób rozumowania jest poprawny:

\(\displaystyle{ a^{n}\equiv a \pmod{n}}\)
\(\displaystyle{ a \cdot a^{n-1}\equiv a \cdot 1 \pmod{n}}\)
\(\displaystyle{ n \mid a \cdot a^{n-1} - a \cdot 1}\)
\(\displaystyle{ n \mid a \cdot (a^{n-1} - 1)}\)

Ostatnie o ile dobrze pamiętam można przedstawić także w postaci, że istnieje takie \(\displaystyle{ k}\) całkowite, że:

\(\displaystyle{ a \cdot (a^{n-1} - 1) = n \cdot k}\)

a zatem (zero oczywiście nie jest liczbą pierwszą):

\(\displaystyle{ k = \frac{a \cdot (a^{n-1} - 1)}{n}}\)

Wiem też, że zachodzi \(\displaystyle{ NWD(a, n) = 1}\), ale nie jestem pewien dlaczego w takim razie możliwe jest skrócenie ułamka do postaci, że istnieje takie \(\displaystyle{ l}\) całkowite, że:

\(\displaystyle{ l = \frac{a^{n-1} - 1}{n}}\)

Jedyne co łopatologicznie przychodzi mi do głowy, to że ułamek "nie skróci się" dla pierwszego czynnika z licznika, gdyż liczby \(\displaystyle{ a}\) i \(\displaystyle{ n}\) nie mają wspólnego dzielnika, a zatem drugi czynnik z licznika musi być "w pełni" podzielny przez mianownik.

[matmatmm]

Twierdzenie brzmi: Jeśli \(\displaystyle{ NWD(a,b)=1}\) oraz \(\displaystyle{ b|ac}\), to \(\displaystyle{ b|c}\).
Dowód jest oparty na dwóch lematach:
1. Jeśli \(\displaystyle{ n|k}\) oraz \(\displaystyle{ m|k}\), to \(\displaystyle{ NWW(m,n)|k}\).
2. \(\displaystyle{ NWW(p,q)\cdot NWD(p,q)=p\cdot q}\)

Liczba \(\displaystyle{ ac}\) jest podzielna zarówno przez \(\displaystyle{ a}\) jak i przez \(\displaystyle{ b}\). Tak więc w myśl lematu 1 przez \(\displaystyle{ NWW(a,b)}\). W myśl założenia i lematu 2 \(\displaystyle{ NWW(a,b)=ab}\). Tak więc \(\displaystyle{ ab|ac}\) i tutaj można już skrócić przez przejście na definicję, czyli \(\displaystyle{ b|c}\).

[gszpetkowski]

Dziękuję bardzo Z mojej strony temat można zamknąć.