Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
You keep referring to $p$ without ever telling us what it is. I suppose $p$ is 101? –  Gerry Myerson Nov 13 '11 at 23:07
    
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? –  Gerry Myerson Nov 13 '11 at 23:10
add comment

1 Answer

up vote 0 down vote accepted

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.

share|improve this answer
    
OK, but how did you figure out that $380204023\equiv 36$ (mod 101)? –  Alison Nov 13 '11 at 23:30
    
(also, I think you mean -380204032) –  Alison Nov 13 '11 at 23:33
    
@MathMastersStudent, if you don't know how to reduce a number mod 101, what exactly are you able to use to solve this problem? –  Gerry Myerson Nov 13 '11 at 23:39
    
Sorry, I'm sick and have a cold and braindead. Yeah, i know how to reduce a number 101. Sorry about that! –  Alison Nov 13 '11 at 23:40
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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