0
$\begingroup$

I understand that for the first step, I just have to find an integer $t$ such that $0\leq t\leq 100$ such that $t^2-56$ is not a perfect square mod $101$. I know that to show that $t^2-56$ is not a perfect square mod $101$, I just have to show that $(t^2-56)^{50}-1$ is not divisible by $101$ (right?). I want to pick a $t$ and calculate. The problem is, is that once I plug in $t$, $(t^2-56)^{50}$ is too large for my calculator to handle. So how do I check that given a $t$, $(t^2-56)^{50}-1$ is not divisible by $101$?

(this is a homework question, and we are allowed to use any internet resources). So far, what we have done in class is prove that the group of units of a finite field is cyclic, and of course Fermat's Little Theorem.

  • 0
    For roughly half the values of $t$ in your range, $t^2-56$ will not be a square mod $p$. So if you just choose values of $t$ any way you like, pretty soon you'll find one for which $t^2-56$ is not a square. So the question is, what goes wrong with the algorithm if $t^2-56$ *is* a square? Maybe when the algorithm goes wrong, you can abandon that $t$ and try another?2011-11-13

1 Answers 1

0

You can reduce the powers $\pmod {101}$ as you go along. So if $t=2, t^2-56=-52, (t^2-56)^5=380 204 032\equiv 36 \pmod {101}$ You can take this to the $5^{th}$ power, reduce mod $101$, and square.

  • 0
    Sorry, I'm sick and have a cold and braindead. Yeah, i know how to reduce a number 101. Sorry about that!2011-11-13