6
$\begingroup$

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?

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

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

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ Reason for the downvoting?? $\endgroup$ – SchrodingersCat Jan 13 '16 at 18:27
  • 1
    $\begingroup$ I didn't downvote, but you didn't explain how tortient(36) =12 implies 36 divides 13788. You just did it. $\endgroup$ – fleablood Jan 13 '16 at 18:38
  • $\begingroup$ ... but then I can't figure it out either. $\endgroup$ – fleablood Jan 13 '16 at 19:00
  • $\begingroup$ 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 $\endgroup$ – Jimbo Jones Jan 13 '16 at 19:42
2
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
1
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ I added the last part, the request to calculate the last part is really frequent and much more related to the $\phi$ function! $\endgroup$ – Maffred Jan 13 '16 at 18:42
  • $\begingroup$ 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. $\endgroup$ – fleablood Jan 13 '16 at 18:58
  • $\begingroup$ In fact, asking for a power of 13788 is much more interesting. $\endgroup$ – Maffred Jan 13 '16 at 18:59
  • 1
    $\begingroup$ I wonder if the question was to calculate $5^{13788} \mod 36$. Showing 36|13788 is pretty simple. $\endgroup$ – fleablood Jan 13 '16 at 19:03
  • $\begingroup$ Yes, probably this is the case! $\endgroup$ – Maffred Jan 13 '16 at 19:09

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.