Liczby pierwsze i kongruencja

Podzielność. Reszty z dzielenia. Kongruencje. Systemy pozycyjne. Równania diofantyczne. Liczby pierwsze i względnie pierwsze. NWW i NWD.
Awatar użytkownika
Tristan
Użytkownik
Użytkownik
Posty: 2353
Rejestracja: 24 kwie 2005, o 14:28
Płeć: Mężczyzna
Podziękował: 27 razy
Pomógł: 557 razy

Liczby pierwsze i kongruencja

Post autor: Tristan »

Wykazać, że jeżeli \(\displaystyle{ p,q}\) są różnymi liczbami pierwszymi, to \(\displaystyle{ p^{q-1} +q^{p-1} \equiv 1 ( mod\ pq)}\).
Awatar użytkownika
Lorek
Użytkownik
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

Post autor: Lorek »

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.
ODPOWIEDZ