1
$\begingroup$

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$

$\endgroup$
  • $\begingroup$ I expanded $4^{2(74)}$ and $4^{2}*4^{2}*4^{2}*4^{2}$. $\endgroup$ – Prime Jul 1 '18 at 22:48
  • $\begingroup$ The $4^{8}$ cancels out, since it's modulus is 1 when we substitute. $4^{8}$ mod $17$ $=$ $1$. $\endgroup$ – Prime Jul 1 '18 at 23:01
  • $\begingroup$ You're absolutely right, the only problem is the single missing factor of 4. $\endgroup$ – David Diaz Jul 1 '18 at 23:03
  • $\begingroup$ Haha I'm off by a whole factor of $4$. I don't really see where, can you point it out? I'm confused by my own work laughs nervously... $\endgroup$ – Prime Jul 1 '18 at 23:04
  • 1
    $\begingroup$ Once you get $710^4 \equiv 1 \mod 17$ you are soooooooo golden!. That means $710^{447} = (710)^4*(710)^4*..............*(710)^4*710^3 \equiv 1*1*1*......*1*4\equiv 4 \mod 17$. Don't bother with any higher powers (actually that's always good advice). $\endgroup$ – fleablood Jul 1 '18 at 23:16
4
$\begingroup$

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

$\endgroup$
  • $\begingroup$ I am aware of Fermat's Little Thm. and its results, but I don't think my professor would like that...he's a bit of a stickler in that way, I guess. And I didn't see the application for this, until now. Good intuition. Now I need to really analyze exactly what you did... $\endgroup$ – Prime Jul 1 '18 at 23:08
  • 1
    $\begingroup$ Well, all I did was take powers of $(-4)$ until I got $(-4)^4 \equiv 1 \mod 17$. And that lets me say $(-4)^{4k}\equiv 1 \mod 17$. So $447 = 444 + 3$ so $(-4)^{447}\equiv (-4)^{3} \mod 17$. $\endgroup$ – fleablood Jul 1 '18 at 23:12
  • 1
    $\begingroup$ Basically I did what you did but I was a bit more focused. $\endgroup$ – fleablood Jul 1 '18 at 23:13
  • $\begingroup$ Also, you were more efficient. Good work. I see you around MSE a lot...👀 $\endgroup$ – Prime Jul 1 '18 at 23:14
  • 1
    $\begingroup$ Yuck. What is k and m? $\endgroup$ – William Elliot Jul 2 '18 at 2:45
2
$\begingroup$

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)

$\endgroup$
0
$\begingroup$

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$.

$\endgroup$
  • $\begingroup$ How do you know that is the correct mod? That is a ridiculous computation (I am speaking about $710^{4}$) How can we simplify this better? $\endgroup$ – Prime Jul 1 '18 at 22:52
  • $\begingroup$ If $710^4=1$ mod $17$, $710^8=710^4\times 710^4 =1\times 1$ mod $17$ and $710^{4n}=1$ mod $17$. $\endgroup$ – Tsemo Aristide Jul 1 '18 at 22:57
  • $\begingroup$ I can get more on board with this $\endgroup$ – Prime Jul 1 '18 at 22:59
0
$\begingroup$

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}$

$\endgroup$
  • $\begingroup$ Can you elaborate on this? $\endgroup$ – Prime Jul 1 '18 at 22:54
  • $\begingroup$ Ah. I imagined it was a silly algebra mistake. $\endgroup$ – Prime Jul 1 '18 at 22:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.