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

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

• Hint: $2016 = 2^5 \times 3^2 \times 7$, so it suffices to show that it is divisble by $2^5$, $3^2$ and $7$. – user133281 Aug 29 '16 at 9:37
• In my opinion this is a duplicate of this generic question. I won't vote to close myself, because some other users will disagree, but.. Anyway, by the comment above $2016$ is a particularly nice case for using the Carmichael function (even though this question was likely designed with just Euler's totient in mind :-) – Jyrki Lahtonen Aug 29 '16 at 10:02

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

• Could you please explain to me how exactly to compute Euler's function - I do not understand it. Thank you! – Teo Aug 29 '16 at 21:57

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

HINT:

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

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}$