1

I want to calculate $24^{6^{2015}}$ mod 35. I found its answer and its correct, but I am not sure if I found it right. It equals 1 mod 35. Here is my calculation:

It follows from Euler theorem: $24^{\phi(35)}$ = 1 mod 35.

$$ \phi(35) = \phi(7)\phi(5) = 6*4 = 24 $$ Thus we want to know $6^{2015}$ mod 24. Now I use Chinese remainder theorem:

($6^{2015}$ mod 24) $\rightarrow$ ($6^{2015}$ mod 8, $6^{2015}$ mod 3)

This gives

($6^{2015}$ mod 8, $0^{2015}$ mod 3) $\rightarrow$ ($6^{2015}$ mod 2, $6^{2015}$ mod 2, $6^{2015}$ mod 2, $0^{2015}$ mod 3)

This gives

($0^{2015}$ mod 2, $0^{2015}$ mod 3)

Now I am not sure if it follows from this that $6^{2015}$ mod 24 = 1 mod 24.

Does this calculation work?

Thank you,

V.

Mithlesh Upadhyay
  • 4,787
V. Voorspel
  • 93
  • 1
    $6^{2015} mod 24 = 0 mod 24$ as it is equivalent to $6 * 6 * 6 * 6^{2012}=24 * 9 * 6^{2012}$ – N74 Jun 25 '17 at 13:05
  • The beginning of your solution is ok in that you identified the need to calculate the remainder of $6^{2015}$ modulo $24$. Surely it is simpler to just observe that $6^{2015}$ is divisible by both $3$ and $8$, and therefore also by $24$? – Jyrki Lahtonen Jun 25 '17 at 13:06

4 Answers4

2

There is no need to use Chinese remainder theorem.

You proved that $24^{24}\equiv 1\pmod{35}$, and you've done the harder part - the rest is totally trivial, since $6^{2015}$ is divisible by $24$ (so $24^{6^{2015}}=24^{24n}\equiv 1^n=1\pmod{35}$ for some $n\in\mathbb{N}$).

tong_nor
  • 3,994
0

You could simply note that $$24^{6^{2015}}\equiv1 \pmod5$$ $$24^{6^{2015}}\equiv3^{6^{2015}}\equiv1 \pmod7$$

So your number is

$$24^{6^{2015}}=35k+1$$ where $k$ is an integer

So the answer is $1$...

LM2357
  • 4,083
0

As Carmichael Function $\lambda(35)=12$

$$24^{6^n}\equiv24^{6^n\pmod{12}}\pmod{35}$$

Now observe that $6^n\equiv0\pmod{12}$ for $n\ge2$

$$\implies24^{6^n}\equiv24^0\pmod{35}$$ for $n\ge2$

lab bhattacharjee
  • 274,582
0

You just note that $6^{2015}$ is exactly divisible by 24 (lots of powers of 2 and 3), so we get $0$ in the exponent, so $1$ in total.

Henno Brandsma
  • 242,131