# Thread: A question on modular arithmetic

1. ## A question on modular arithmetic

I'm preparing for a contest, and for some of the practice questions, I've managed to simplify things greatly, but I can't figure out how to simplify what I have further.

For example:
17^17 mod 25
18^16 mod 25
19^19 mod 25

How do I simplify these expressions any further...
I don't think CRT and Euler's formula can help me any further.

2. I got 18^16 mod 25.
Since 18^4 = 1 mod 25, we have
18^16 = 1 mod 25.

3. For instance,

All mod 25

17^17
= (-8)^17
= -8 * (-8)^16
= -8 * 64^8
= -8 * 14^8
= -8 * 196 ^ 4
= -8 * (-4)^4
= -8 * 256
= -8 * 6
= -48
= 2

4. Hello, elemental!

$\displaystyle 18^{16}\text{ mod 25}$

$\displaystyle \text{Since }18^4 \equiv 1\text{ (mod 25)}$

. . $\displaystyle \text{we have: }\:(18^4)^4 \,\equiv\,1^4\text{ (mod 25)}$

$\displaystyle \text{Therefore: }\:18^{16} \:\equiv\:1\text{ (mod 25)}$ . Good!

$\displaystyle 17^{17}\text{ (mod 25)}$

We have: .$\displaystyle 17\:\equiv\:\text{-}8\text{ (mod 25)}$

$\displaystyle (\text{-}8)^4 \:=\:4096 \:\equiv\:\text{-}4\text{ (mod 25)}$

$\displaystyle [(\text{-}8)^4]^4 \:\equiv\:(\text{-}4)^4 \:\equiv\:256\text{ (mod 25)}$

$\displaystyle (\text{-}8)^{16} \:\equiv\:6\text{ (mod 25)}$

$\displaystyle (\text{-}8)^{16}\cdot(\text{-}8) \:\equiv\:6\cdot(\text{-}8) \text{ (mod 25)}$

$\displaystyle (\text{-}8)^{17} \:\equiv\:-48\text{ (mod 25)}$

$\displaystyle \text{Therefore: }\:17^{17} \:\equiv\:2\text{ (mod 25)}$

$\displaystyle 19^{19}\text{ (mod 25)}$

$\displaystyle \text{We have: }\:19 \:\equiv\:\text{-}6\text{ (mod 25)}$

$\displaystyle (\text{-}6)^4 \;=\;1296 \:\equiv\:\text{-}4\text{ (mod 25)}$

$\displaystyle [(\text{-}6)^4]^4 \:\equiv\:(\text{-}4)^4 \:\equiv\:256\text{ (mod 25)}$

$\displaystyle (\text{-}6)^{16} \:\equiv\:6\text{ (mod 25)}$

$\displaystyle (\text{-}6)^{16}\!\cdot\!(\text{-}6)^3 \:\equiv\:6\!\cdot\!(\text{-}6)^3 \text{ (mod 25)}$

$\displaystyle (\text{-}6)^{19} \:\equiv\:\text{-}1296\text{ (mod 25)}$

$\displaystyle \text{Therefore: }\:19^{19} \:\equiv\:4\text{ (mod 25)}$

5. Thanks... I got it differently, though.

I just used Euler's formula again.
Since phi(25) = 20, we know
17^20 = 1 mod 25.

We know 3 = 17^-1 mod 25.

So 17^17 = 3^3 = 2 mod 25.

6. A different approach is by the Binomial Theorem.

We have $\displaystyle 17\equiv2\pmod5$, namely $\displaystyle 17=2+5k$, where $\displaystyle k$ is some integer. Then $\displaystyle (2+5k)^5=2^5+\binom{5}{1}\cdot2^4(5k)^1+\binom{5}{ 2}\cdot2^3(5k)^2+\binom{5}{3}\cdot2^2(5k)^3+\binom {5}{4}\cdot2^1(5k)^5+(5k)^5$ by the Binomial Theorem.
Note that all the terms except for the first one are divisible by 25. Therefore, $\displaystyle 17^5\equiv2^5\equiv7\pmod{25}$. Hence, $\displaystyle 17^{17}=(17^5)^3\cdot17^2\equiv7^3\cdot17^2\equiv(-7)\cdot14\equiv2\pmod {25}$.

Similarly, from the congruence $\displaystyle 18\equiv3\pmod5$ it follows that $\displaystyle 18^5\equiv3^5\equiv(-7)\pmod{25}$, so $\displaystyle 18^{16}=18^5\cdot18\equiv(-7)\cdot(-7)\equiv1\pmod{25}$.

Again $\displaystyle 19\equiv4\pmod5$ and then $\displaystyle 19^5\equiv4^5\equiv(-1)\pmod{25}$. Therefore $\displaystyle 19^{19}=(19^5)^3\cdot19^4\equiv(-1)^3\cdot19^4$; so $\displaystyle 19^4=19^2\cdot19^2\equiv11\cdot11\equiv(-4)\pmod {25}$ gives $\displaystyle 19^{19}\equiv4\pmod{25}$.

7. Originally Posted by qmech
For instance,

All mod 25

17^17
= (-8)^17
= -8 * (-8)^16
= -8 * 64^8
= -8 * 14^8

*** $\displaystyle 64=13\!\!\pmod {17}$ ***

= -8 * 196 ^ 4
= -8 * (-4)^4
= -8 * 256
= -8 * 6
= -48
= 2
*** $\displaystyle -48=3\!\!\pmod{17}$...and nevertheless the result is correct! Mistake + mistake = correct.

Tonio