how to solve $\operatorname{rem}(6^{15},17)$ without using a calculator.

Question

I am trying to solve $\operatorname{rem}(6^{15}, 17)$.

I know that we have to use congruences but don't know how to go on.

$6 ≅ 6 \mod 17$??

Can anyone please point me in the right direction?

Do I have to use CRT in here?

user · Answer 1 · 2019-09-30T21:56:08.960

4

HINT

Recall that by Fermat's little theorem

$$6^{16}\equiv 1 \mod 17$$

that is for some $k\in \mathbb Z$

$$6^{16}=k\cdot 17+1$$

edited Sep 30 '19 at 21:56

answered Sep 30 '19 at 21:47

user

Bernard · Answer 2 · 2019-09-30T22:00:21.500

1

You need lil' Fermat and a Bézout's relation between $6$ and $17$, as Fermat implies that $6^{15}\equiv 6^{-1}\mod 17$.

Some more details:

A Bézout's relation between $6$ and $17$ is obviously $\;3\cdot 6-17=1$, which implies $6^{-1}\equiv 3\bmod 17$.

edited Sep 30 '19 at 22:00

answered Sep 30 '19 at 21:52

Bernard

i have not heard about this relation? could you please elaborate a little bit more? – sashank88 Sep 30 '19 at 21:53
Great Bernard :o)....+1. – Sebastiano Sep 30 '19 at 21:56
It is the relation which characterises coprime integers, and gives the inverse of an integer modulo the other. I'll add some details – Bernard Sep 30 '19 at 21:57
so from both equation do you get 6^{15} ≡ 3 mod 17? is 3 the answer? – sashank88 Sep 30 '19 at 22:09
Yes, absolutely. – Bernard Sep 30 '19 at 22:13
thank you. i really appreciate it. – sashank88 Sep 30 '19 at 22:21

score 0 · Accepted Answer · answered Sep 30 '19 at 22:28

A low tech solution:

$6^2 = 36 \equiv 2 \pmod{17}$ ($34$ is a multiple of $17$).

So $6^4 = (6^2)^2 \equiv 2^2 = 4 \pmod{17}$

Hence: $6^8 = (6^4)^2 \equiv 4^2 = 16 \equiv -1 \pmod{17}$

Also: $6^{15}=6^1 \cdot 6^2 \cdot 6^4 \cdot 6^8$ ($15$ is $1111$ in binary), so modulo $17$ this becomes

$6 \times 2 \times 4 \times -1 = -48 \equiv -48 + 3\times 17 = 3$

So $3$ is the answer.

3 Answers3