Małe twierdzenie Fermata, postać skrócona
: 25 lis 2013, o 18:03
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.
\(\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.