Zeigen Sie, dass } a^{(p-1)(q-1)} \equiv 1 \pmod{pq}.

Question

\( \text{Seien } p, q \text{ verschiedene Primzahlen, } a \text{ eine natürliche Zahl, die nicht} \\ \text{durch } p \text{ oder } q \text{ teilbar ist. Zeigen Sie, dass } a^{(p-1)(q-1)} \equiv 1 \pmod{pq}. \)

Answer 1

Vermutlich hattet ihr für Primzahlen schon \(  a^{p-1} \equiv 1 \mod p   \)

und weil q*p ein Vielfaches von p ist auch   \(  a^{p-1} \equiv 1 \mod p \cdot q \) .

==>     \(  a^{(p-1) \cdot (q-1) }   \equiv (a^{p-1})^{q-1} \equiv 1^{q-1}   \equiv 1 \mod   p \cdot q   \)