Kongruencja, MTF

[Papkin]

Załóżmy, że
\(\displaystyle{ p,q P\backslash \lbrace 2 \rbrace}\)
oraz
\(\displaystyle{ p-1|q-1}\)
Wykazać:
\(\displaystyle{ (a,pq)=1 a^{q-1} \equiv a(mod pq)}\)
P to zbiór liczb pierwszych. Z góry dziękuje za rozwiązanie.

[Sylwek]

Chyba chodziło o \(\displaystyle{ a^{q-1} \equiv 1 \ (mod \ pq)}\). Gdy p=q teza jest fałszywa , zatem dopisuję założenie \(\displaystyle{ p q}\).

Mamy: \(\displaystyle{ \frac{q-1}{p-1}=k, \ k \mathbb{Z_+}}\), wówczas z MTF:
\(\displaystyle{ a^{p-1} \equiv 1 \ (mod \ p)}\), podnosimy do k-tej:
\(\displaystyle{ (a^{p-1})^k=\ldots=a^{q-1} \equiv 1^k=1 \ (mod \ p)}\)

Analogicznie z MTF:
\(\displaystyle{ a^{q-1} \equiv 1 \ (mod \ q)}\), lecz ponieważ \(\displaystyle{ (p,q)=1}\), to:

\(\displaystyle{ a^{q-1} \equiv 1 \ (mod \ (p q)) \iff a^{q-1} \equiv 1 \ (mod \ pq)}\)