Modulus and Exponents

Question

The question:

Determine $N$ where $0$ $\leq$ $n$ $\leq$ $16$ such that $710^{447}$$\equiv$ $n$ $($ mod $17$ $)$

My attempt

$710^{1}$ $\equiv$ $710$ (mod $17$) $\equiv$ $13$

$710^{2}$ $\equiv$ $13^{2}$ $\equiv$ $169$ (mod $17$) $\equiv$ $16$

$710^{3}$ $\equiv$ $16*13$ $\equiv$ $208$ (mod $17$) $\equiv$ $4$

$710^{4}$ $\equiv$ $16^{2}$ $\equiv$ $256$ (mod $17$) $\equiv$ $1$

$710^{5}$ $\equiv$ $16^{2}*13$ $\equiv$ $3328$ (mod $17$) $\equiv$ $13$

$710^{6}$ $\equiv$ $4^{2}$ $\equiv$ $16$ (mod $17$) $\equiv$ $16$

$710^{7}$ $\equiv$ $16*4*13$ $\equiv$ $832$ (mod $17$) $\equiv$ $16$

It follows,

$$710^{3(149)}\equiv4^{148+1}\equiv4^{148}*4^{1}\equiv4^{2(74)} *4^{1}$$ $$4^{2(74)}*4^{1}\equiv4^{8}*4^{5(7)}*4^{5(7)}*4^{5(7)}*4^{5(7)}*4^{1}$$

$$65536 (mod 17) \equiv 1$$

So,

$$4^{8}*4^{5(7)}*4^{5(7)}*4^{5(7)}*4^{5(7)}\equiv4^{140}$$

And,

$$4^{140}\equiv4^{4*5*7}$$

Since $$4^{4}=256$$

We obtain $$256 (mod 17) \equiv 1$$

and, $$1^{5*7}=1$$

Thus, $N$=$1$

Answer 1

Do you know Fermats Little theorem that states if $p$ is prime (as $17$ is) and $a\not \equiv 0 \mod p$ then $a^{p-1} \equiv 1 \mod p$.

So $710^{447}= 710^{16k + m} \equiv 710^{16k}710^m \equiv 710^m \mod 17$.

If not:

$710 = 41*17 + 13 \equiv 13\equiv -4 \mod 17$. ($4$ is a much nicer number than $13$).

$710^2 \equiv (-4)^2 = 16 \equiv -1 \mod 17$. ($1$ is as nice as you can get.)

$710^4 \equiv (-1)^2 \equiv 1 \mod 17$.

$710^{444} = (710^4)^{111} \equiv 1^{111}\equiv 1 \mod 17$.

So $710^{447}\equiv 1*710^3 \equiv (-4)^3 \equiv (-4)^2*(-4)\equiv (-1)*(-4) \equiv 4 \mod 17$.

But, yes, what you did looks okay but there's an error somewhere.

....

Once your realize that $710^4 \equiv 1 \mod 17$ it may, or may not, be worth noting that $710^{4k} \equiv 1 \mod 17; 710^{4k + 1} \equiv 13 \mod 17; 710^{4k +2} \equiv 16 \mod 17; 710^{4k + 3}\equiv 4 \mod 17$. And that is all of the congruences

Answer 2

If you have $710^4=1$ mod $17$ it implies that $710^{4n}=1$ mod $17$, since $447=444+3=4(111)+3$, you deduce that $710^{447}=710^3$ mod $17= 3$ mod $17$.

Answer 3

Once you have $710^{447} \equiv 4^{149}\equiv 4^{2(74)}\times 4$, note that $4^2 \equiv -1 \pmod {17}$

Your work is fine except that you lost a factor of 4 after "So,". You went from considering $4^{149}$ in the previous paragraph to considering $4^{148}$ in the rest of your work.

As you note in your scratchwork, $n^a\times n^b = n^{a+b}$ and $(n^{a})^{b} \equiv n^{ab}$

Hint: Since $4^2 = 16 \equiv -1\pmod {17}$ Then $4^{2(74)} \equiv (4^{2})^{74}\equiv (-1)^{74}$

Answer 4

710 = 41 * 17 + 13 = 42 * 17 - 4
447 = 27 * 16 + 15

As 710 /= 0 (mod 17), by Fermat's little theorem
710^16 = 1 (mod 17).

Thus 710^447 = (-4)^15 (mod 17)

-4 * (-4)^15 = 1 (mod 17); -4 * 4 = 1 (mod 17)
(-4)^15 = 4 (mod 17) since $Z_{17}$ is a field.

710^447 = 4 (mod 17)