Calculate $\phi(36)$, where $\phi$ is the Euler Totient function. Use this to calculate $13788 \pmod {36}$.

Question

I am wondering if anyone can help me. I am trying to figure out how to

Calculate $\phi(36)$, where $\phi$ is the Euler Totient function. Use this to calculate $13788 \pmod {36}$.

I have an exam coming up an this will be one style of question. Can anyone please walk me through how it is done?

Thanks to SchrodingersCat I now know first part is $12$.

The second part should be along the lines of below but I do not understand how this was arrived at. \begin{align} 13788 \pmod {36} &= 13788 \pmod {\phi(36)} \pmod {36} \\ &= 13788 \pmod {12} \pmod {36} \\ &= 138 \pmod {36} \\ &= ((132)2)2 \pmod {36} \\ &= (252)2 \pmod {36} \\ &= 132 \pmod {36} \\ &= 25 \end{align}

Can anyone show me why it is $25$ and how do I get it?

Answer 1

$$36=2^2\cdot 3^2$$

So $$\phi(36)=36\cdot \left(1-\frac{1}{2}\right)\left( 1-\frac{1}{3}\right)=12$$

If you are unaware of this formula, then check this link and also the example there.

For the second part, observe that $13788=2^2\cdot 3^2\cdot 383$

So $36$ divides $13788$.

That is, $$13788 \equiv 0 \pmod {36}$$

Answer 2

Remember that:

$\phi(p)=p-1$

$\phi(p^n) = p^n -p^{n-1}$

for every prime number $p$.

And $\phi(ab)=\phi(a)\phi(b)$ whenever $a$ and $b$ are relatively prime.

Thus $\phi(36) = \phi(9)\phi(4)=\phi(3^2)\phi(2^2)=(9-3)(4-2)=12$.

We are lucky since

$13788 = 383\cdot 36$

and so

$13788 = 383\cdot 36 \equiv 0 \pmod{36}$.

If you want to compute $a^{13788}$ modulo $36$ when $a$ and $36$ are relatively prime, you can use Little Fermat Theorem which says that

$a^{\phi(36)} \equiv 1 \pmod{36}$.

You get

$a^{13788} = (a^{12})^{1149} \equiv 1^{1149} \equiv 1 \pmod{36}$.