Liczby pierwsze i kongruencja
- Lorek
- Użytkownik
- Posty: 7150
- Rejestracja: 2 sty 2006, o 22:17
- Płeć: Mężczyzna
- Lokalizacja: Ruda Śląska
- Podziękował: 1 raz
- Pomógł: 1322 razy
Liczby pierwsze i kongruencja
Skorzystamy z MTF. Wiemy, że
\(\displaystyle{ p|q^{p-1}-1\Rightarrow q^{p-1}-1\equiv 0\pmod p \\q|p^{q-1}-1\Rightarrow p^{q-1}-1\equiv 0 od q}\)
ponadto
\(\displaystyle{ p^{q-1}\equiv 0\pmod p\\q^{p-1}\equiv 0\pmod q}\)
wynika z tego, że
\(\displaystyle{ p^{q-1}+q^{p-1}-1\equiv 0\pmod p\\p^{q-1}+q^{p-1}-1\equiv 0\pmod q}\)
a ponieważ p,q są różnymi liczbami pierwszymi, to
\(\displaystyle{ p^{q-1}+q^{p-1}-1\equiv 0 od {pq}\\p^{q-1}+q^{p-1}\equiv 1\pmod {pq}}\)
cnd.
\(\displaystyle{ p|q^{p-1}-1\Rightarrow q^{p-1}-1\equiv 0\pmod p \\q|p^{q-1}-1\Rightarrow p^{q-1}-1\equiv 0 od q}\)
ponadto
\(\displaystyle{ p^{q-1}\equiv 0\pmod p\\q^{p-1}\equiv 0\pmod q}\)
wynika z tego, że
\(\displaystyle{ p^{q-1}+q^{p-1}-1\equiv 0\pmod p\\p^{q-1}+q^{p-1}-1\equiv 0\pmod q}\)
a ponieważ p,q są różnymi liczbami pierwszymi, to
\(\displaystyle{ p^{q-1}+q^{p-1}-1\equiv 0 od {pq}\\p^{q-1}+q^{p-1}\equiv 1\pmod {pq}}\)
cnd.