Use Euler's theorem to prove that:

For any odd integer a, $a^{33} \equiv a \pmod {4080}.$

The hint given in the book is that $4080 = 15 \times 16 \times 17$, but I do not know how to use Euler's theorem to deal with $n = 15,17$,the condition $gcd (a,n) =1$ is not satisfied in those cases, could anyone clarify this for me please?

  • $\begingroup$ Why did you tag your question under "convergence"? $\endgroup$ – uniquesolution May 31 '19 at 5:45
  • $\begingroup$ I am sorry it was a mistake@uniquesolution $\endgroup$ – Secretly May 31 '19 at 5:52

Euler's theorem for primes (Also known as Fermat's little theorem) tells you that $a^{p-1}\equiv 1\mod p$ if $\gcd(p,a)=1$.

For $p=3$ you have

$a^2\equiv 1\mod 3$ if $\gcd (a,3)=1$. So, $a^{33}\equiv (a^2)^{16}a\equiv a\bmod 3$ if$\gcd (a,3)=1$. But note that $a^{33}\equiv a\bmod 3$ also in the case when $3|a$ (in that case $a^{33}\equiv a\equiv 0\bmod 3$.)

So, $a^{33}\equiv a\mod 3$ for all $a$.

Do the same for $p=5$, $p=17$ and prove that $a^{33}\equiv a\mod 5$ and $a^{33}\equiv a\mod 17$.

Finally, since $a$ is odd, $\gcd(16,a)=1$. So, Euler's theorem tells you that $a^8\equiv 1\mod 16$. Conclude from here that $a^{33}\equiv a\mod 16$.

If you have $a^{33}\equiv a$ mod 3,5,16,17. Then you have your result.

Short answer: Since $\varphi(3)$,$\varphi(5)$,$\varphi(17)$,$\varphi(16)$ are divisors of $32$. Then $a^{33}\equiv a\mod(3\times 5\times 17\times 16).$

| cite | improve this answer | |

Using Fermat's Little Theorem

$17$ divides $a^{16m+1}-a$

$3$ divides $a^{2n+1}-a$

$5$ divides $a^{4p+1}-a$

So, we need $16m=2n=4p\implies n=8m,p=4m$

Using Carmichael Function as $a$ is odd $$a^{2^n}\equiv1\pmod{2^{n+2}}$$ for $n\ge2$

If $n=4\implies2^{4+2}$ divides $a^{16}-1$ which again divides $(a^{16})^r-1^r$

$\implies2^6$ divides $a^t-1$ if $16|t$

So, $a^{16m+1}-a$ will be divisible by lcm of $(3,5,17,2^6)$

Here $16m+1=33$

| cite | improve this answer | |

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.