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

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?

• Hint: the totient function is multiplicative. That is $\phi(ab) = \phi(a)\phi(b)$. – Colm Bhandal Jan 13 '16 at 18:19
• Was the question to calculate 13788 mod 36. Or to calculate $b^{13788} \mod 36$ for $b =$ some odd number not divisible by 3? – fleablood Jan 13 '16 at 19:08

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

• Reason for the downvoting?? – SchrodingersCat Jan 13 '16 at 18:27
• I didn't downvote, but you didn't explain how tortient(36) =12 implies 36 divides 13788. You just did it. – fleablood Jan 13 '16 at 18:38
• ... but then I can't figure it out either. – fleablood Jan 13 '16 at 19:00
• The answer for the second part is: 13788 (mod 36) = 13788 (mod φ(36)) (mod 36) = 13788 (mod 12) (mod 36) = 138 (mod 36) =((132)2)2(mod 36) = (252)2(mod 36) = 132(mod 36) = 25, but I can not figure out how this answer was achieved – Jimbo Jones Jan 13 '16 at 19:42

$36=4\times9$

Since $4$ and $9$ are relatively prime, we have

$\phi(36)=\phi(4)\phi(9)$

Using the identity that for any prime $p$, $\phi(p^n)=p^n-p^{n-1}$

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

As for the second part of the question, then, 13788 (mod 12) (mod 36) $\ne 138(mod 36)$ and hence your question is wrong.

There seems to be typo error and this part of the question can be modified to $13^{788}(mod\ 36) = 13^{788(mod \phi(36))}(mod\ 36) = 13^{788(mod 12)}(mod\ 36)=13^8(mod\ 36)=25$

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

• I added the last part, the request to calculate the last part is really frequent and much more related to the $\phi$ function! – Maffred Jan 13 '16 at 18:42
• Except it doesn't tell us how to calculate 13788 mod 36 ... which I admit, the relevence of the tortient function is escaping me. I thought maybe 13789 was the twelvth root of something but ... no. – fleablood Jan 13 '16 at 18:58
• In fact, asking for a power of 13788 is much more interesting. – Maffred Jan 13 '16 at 18:59
• I wonder if the question was to calculate $5^{13788} \mod 36$. Showing 36|13788 is pretty simple. – fleablood Jan 13 '16 at 19:03
• Yes, probably this is the case! – Maffred Jan 13 '16 at 19:09