Exponents and mod (Euler's theorem)

Question

I know how to compute $7^{402} \pmod{10}$ using Euler's theorem since $7$ and $10$ are relatively prime.

But is there an easy way without using a calculator to compute $12^{720} \pmod{10}$. I don't think Euler's Theorem can be applied because $12$ and $10$ are not relatively prime...

Also, for $5^{1806} \pmod{63}$, finding $\varphi(63)$ is kinda difficult. Is there an easy way to solve that?

Answer 1

First observe $(12)^{720} \equiv (2)^{720} \pmod {10}$ (I think this is obvious). Anyways we can easily prove it using binomial theorem on $(2+10)^{270}$

Now, try to find $x$ such that $2^{719} \equiv x \pmod 5$. This is easy by Euler's theorem.

$2^{719} \equiv 3 \pmod 5$.

So, $2^{720} \equiv 6 \pmod {10}$.

For your second question,

$5^{1806} \equiv 125^{602} \equiv (63 \times 2 -1)^{602} \equiv (-1)^{602} \equiv 1 \pmod {63}$.

Answer 2

As $(12,10)=2$

let us find $12^{720-1}\pmod{\dfrac{10}{(12,10)}}$

Now $12\equiv2\pmod5,12^4\equiv2^4\equiv1\implies12^{719}\equiv2^{719}\equiv2^{-1}\equiv3$

$\implies12^{719}\cdot12\equiv3\cdot12\pmod{10}\equiv6$

---

For $5^{1806}\pmod{63},$ use Carmichael function $\lambda(63)=6$ and $1806\equiv0\pmod6$

Answer 3

We could use the idea of the Chinese Remainder Theorem

$12^{720}=3^{720}4^{720}$ is clearly divisible by $2$ so it is one of ${2,4,6,8,10}$ ;we check them mod $5$. Since $6 \equiv 1 \pmod 5$ we conclude $12^{720}\equiv 6 \pmod{10}$

For your last question, use the fact that the totient function is multiplicative to easily calculate the function at larger numbers. In your case $\varphi(63)=\varphi(9)\varphi(7)=36$ and in general $$\varphi(nm)=\varphi(n)\varphi(m)$$ If $n$ and $m$ are coprime.

Answer 4

I would refer you to the modular exponentiation article on Wikipedia.

Answer 5

First, note that $n\in\mathbb{N}\implies12^{n}\equiv2^{n}\pmod{10}$.

Second, note that $n\in\mathbb{N}\implies2^{n}\equiv2^{n+4}\pmod{10}$.

Hence $12^{720}\equiv2^{720}\equiv2^{716}\equiv\ldots\equiv2^{4}\equiv16\equiv6\pmod{10}$.