Check if an expression is divisible by 2016. (modulo operations?)

Question

How to check whether $29^{576} - 1$ can be divided by $2016$ without computing the numbers? I suppose that I have to use modular arithmetic, but don't really know how...

Answer 1

Compute Euler's function $\varphi(2016)$.

Then recall that if $\gcd(a, n) = 1$, then $a^{\varphi(n)} \equiv 1 \pmod{n}$, i.e., the remainder of the division of $a^{\varphi(n)}$ by $n$ is $1$.

Answer 2

Hint: Euler's theorem states that $a^{\phi(n)}-1$ is divisible by $n$ whenever $a$ and $n$ are coprime. What is $\phi(2016)$?

Answer 3

HINT:

By Euler's theorem: $\gcd(29,2016)=1\implies29^{\phi(2016)}\equiv1\pmod{2016}$.

Answer 4

As $(29,2016)=1$

use Carmichael Function $\lambda(2016)=$lcm$(2^3,6,6)=24$

As $576\equiv0\pmod{24},29^{576}\equiv29^0\pmod{2016}$