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.
Małe twierdzenie Fermata, postać skrócona
-
- Użytkownik
- Posty: 11
- Rejestracja: 25 lis 2013, o 16:59
- Płeć: Mężczyzna
- Lokalizacja: Kraków
Małe twierdzenie Fermata, postać skrócona
Ostatnio zmieniony 25 lis 2013, o 21:39 przez gszpetkowski, łącznie zmieniany 1 raz.
-
- Użytkownik
- Posty: 2282
- Rejestracja: 14 cze 2011, o 11:34
- Płeć: Mężczyzna
- Lokalizacja: Sosnowiec
- Podziękował: 88 razy
- Pomógł: 351 razy
Małe twierdzenia Fermata, postać skrócona
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}\).
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}\).
-
- Użytkownik
- Posty: 11
- Rejestracja: 25 lis 2013, o 16:59
- Płeć: Mężczyzna
- Lokalizacja: Kraków