A question on modular arithmetic

**elemental** · November 18th 2010, 11:05 AM

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.

**elemental** · November 18th 2010, 02:12 PM

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

**qmech** · November 18th 2010, 04:26 PM

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

**Soroban** · November 18th 2010, 05:24 PM

Hello, elemental!

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

**elemental** · November 18th 2010, 05:34 PM

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.

**melese** · November 19th 2010, 02:32 AM

A different approach is by the Binomial Theorem.

We have $17\equiv2\pmod5$ , namely $17=2+5k$ , where $k$ is some integer. Then $(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, $17^5\equiv2^5\equiv7\pmod{25}$ . Hence, $17^{17}=(17^5)^3\cdot17^2\equiv7^3\cdot17^2\equiv(-7)\cdot14\equiv2\pmod {25}$ .

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

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

**tonio** · November 19th 2010, 04:25 AM

Originally Posted by qmech

For instance,

All mod 25

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

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

= -8 * 196 ^ 4
= -8 * (-4)^4
= -8 * 256
= -8 * 6
= -48
= 2

*** $-48=3\!\!\pmod{17}$ ...and nevertheless the result is correct! Mistake + mistake = correct.

Tonio

Thread: A question on modular arithmetic

LinkBack

Thread Tools

Display

A question on modular arithmetic

Similar Math Help Forum Discussions

What is this modular arithmetic question asking exactly?

modular arithmetic

Modular Arithmetic- Quick question

Quick question on graphs and modular arithmetic

Modular arithmetic

Search Tags