Prove that a^13≡ apmod30 for all a coprime to 30, and check with a=7.

It is true, because a^12≡ 1 modulo 3 and modulo 5, and 30=2· 3· 5

It is false, because 7^13not≡ 7pmod30

It is true, because φ(30)=8 and 13≡ 1pmod 8

It is false, because φ(30)=10 and the exponent is not a multiple of 10

Exercise · ZW-EULER-S-THEOREM-010 · ★★★ Advanced

Prove that \(a^{13}\equiv a\pmod{30}\) for all \(a\) coprime to 30, and check with \(a=7\).

Choose one option.

Show answer

A. It is true, because \(a^{12}\equiv 1\) modulo 3 and modulo 5, and \(30=2\cdot 3\cdot 5\)

Explanation

The statement is true: \(30=2\cdot 3\cdot 5\), and for \(a\) coprime to 30, \(a^{12}\equiv 1\) modulo 3 and 5, so \(a^{13}\equiv a\) modulo 3 and 5, and it is trivial modulo 2. For \(a=7\), \(7^{13}\equiv 7 \pmod{30}\).

Study Elementary number theory in ZWMath →

Review the concept: Euler's theorem

Euler's theorem states that if \(a\) and \(n\) are coprime, then \(a^{\varphi(n)} \equiv 1 \pmod{n}\), generalizing Fermat's little theorem to composite moduli.

\[a^{\varphi(n)} \equiv 1 \pmod{n}, \quad \gcd(a,n)=1\]

Prove that \(a^{13}\equiv a\pmod{30}\) for all \(a\) coprime to 30, and check with \(a=7\).

Explanation

Review the concept: Euler's theorem

More practice problems: euler's theorem