0
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ 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$. $\endgroup$ – user133281 Aug 29 '16 at 9:37
  • $\begingroup$ 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 :-) $\endgroup$ – Jyrki Lahtonen Aug 29 '16 at 10:02
2
$\begingroup$

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

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

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

$\endgroup$
0
$\begingroup$

HINT:

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

$\endgroup$
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.