Udowodnij ze jeżeli q>2 jest liczbą pierwszą i NWD(a, b)=1, to każdy dzielnik pierwszy p \(\displaystyle{ \neq}\)q liczby:
\(\displaystyle{ a ^{q-1}+a ^{q-2}b+.....ab ^{q-2} +b ^{q-1}}\)
jest postaci \(\displaystyle{ p=2qm+1}\) (m należy do naturalnych)
małe tw. Fermata. Dzielnk pierwszy p=2qm +1
małe tw. Fermata. Dzielnk pierwszy p=2qm +1
Niech \(\displaystyle{ p}\) będzie dzielnikiem liczby \(\displaystyle{ X=a^{q-1} + a^{q-2} b + \ldots + b^{q-1}}\), czyli \(\displaystyle{ X \equiv 0 \pmod{p}}\).
Gdyby \(\displaystyle{ a\equiv b \pmod{p}}\), to \(\displaystyle{ X \equiv q a^{q-1} \equiv 0 \pmod{p}}\). Ale \(\displaystyle{ q \not \equiv 0 \pmod{p}}\) skąd \(\displaystyle{ a \equiv 0 \pmod{p}}\) oraz \(\displaystyle{ a\equiv b \pmod{p}}\) czyli \(\displaystyle{ (a,b)\ge p > 1}\) sprzeczność.
Wobec tego \(\displaystyle{ a-b\not \equiv 0\pmod{p}}\) czyli
\(\displaystyle{ 0 \equiv 0(a-b) \equiv X(a-b)=a^q - b^q \pmod{p}}\)
co daje
\(\displaystyle{ \left( \frac{a}{b} \right) ^{q} \equiv 1 \pmod{p}}\)
Niech \(\displaystyle{ d}\) będzie rzędem \(\displaystyle{ \frac{a}{b}}\) modulo \(\displaystyle{ p}\). Wtedy z MTF mamy
\(\displaystyle{ d|q \quad \wedge \quad d|p-1}\). Pierwszy warunek daje nam \(\displaystyle{ d=q}\) czyli w połączeniu z drugim \(\displaystyle{ p=kq+1}\). Ale gdyby \(\displaystyle{ 2 \nmid k}\) to \(\displaystyle{ p}\) byłoby parzyste, czyli \(\displaystyle{ p=2}\) skąd \(\displaystyle{ q =1}\), czyli sprzeczność. Wobec tego istotnie \(\displaystyle{ p=2mq+1}\).
Gdyby \(\displaystyle{ a\equiv b \pmod{p}}\), to \(\displaystyle{ X \equiv q a^{q-1} \equiv 0 \pmod{p}}\). Ale \(\displaystyle{ q \not \equiv 0 \pmod{p}}\) skąd \(\displaystyle{ a \equiv 0 \pmod{p}}\) oraz \(\displaystyle{ a\equiv b \pmod{p}}\) czyli \(\displaystyle{ (a,b)\ge p > 1}\) sprzeczność.
Wobec tego \(\displaystyle{ a-b\not \equiv 0\pmod{p}}\) czyli
\(\displaystyle{ 0 \equiv 0(a-b) \equiv X(a-b)=a^q - b^q \pmod{p}}\)
co daje
\(\displaystyle{ \left( \frac{a}{b} \right) ^{q} \equiv 1 \pmod{p}}\)
Niech \(\displaystyle{ d}\) będzie rzędem \(\displaystyle{ \frac{a}{b}}\) modulo \(\displaystyle{ p}\). Wtedy z MTF mamy
\(\displaystyle{ d|q \quad \wedge \quad d|p-1}\). Pierwszy warunek daje nam \(\displaystyle{ d=q}\) czyli w połączeniu z drugim \(\displaystyle{ p=kq+1}\). Ale gdyby \(\displaystyle{ 2 \nmid k}\) to \(\displaystyle{ p}\) byłoby parzyste, czyli \(\displaystyle{ p=2}\) skąd \(\displaystyle{ q =1}\), czyli sprzeczność. Wobec tego istotnie \(\displaystyle{ p=2mq+1}\).
-
- Użytkownik
- Posty: 306
- Rejestracja: 10 maja 2008, o 11:38
- Płeć: Mężczyzna
- Lokalizacja: Toruń
- Pomógł: 36 razy
- Sylwek
- Użytkownik
- Posty: 2716
- Rejestracja: 21 maja 2007, o 14:24
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 160 razy
- Pomógł: 657 razy
małe tw. Fermata. Dzielnk pierwszy p=2qm +1
\(\displaystyle{ \frac{a}{b}= a \cdot b^{-1}}\), czyli a razy odwrotność b w ciele \(\displaystyle{ \mathbb{Z}_p}\) (np. \(\displaystyle{ 2^{-1} (mod \ 5) = 3}\), bo \(\displaystyle{ 2 \cdot 3 \equiv 1 \ (mod \ 5)}\).
Rząd x modulo p to najmniejsza liczba całkowita dodatnia q taka, że \(\displaystyle{ x^q \equiv 1 \ (mod \ p)}\).
Rząd x modulo p to najmniejsza liczba całkowita dodatnia q taka, że \(\displaystyle{ x^q \equiv 1 \ (mod \ p)}\).