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.

Is 13 a quadratic residue of 257. Given that 257 is prime.

I have tried doing it. My study guide says it is true. But I keep getting false.

share|improve this question
4  
Maybe the thing to do is show how you come to the conclusion that it's false, then people could critique your work. –  Gerry Myerson Dec 5 '12 at 2:12
    
What's the contribution of the triple question mark to the title? –  joriki Dec 5 '12 at 5:15

2 Answers 2

up vote 5 down vote accepted

We use somewhat heavy machinery, Quadratic Reciprocity. For typing convenience, we use the notation $(a/p)$ for the Legendre symbol. By Reciprocity, $$(13/257)=(257/13)=(10/13)=(2/13)(5/13).$$ This is because at least one of $13$ and $257$ (indeed both) is of the shape $4k+1$.

Note that $(2/13)=-1$ because $13$ is of the shape $8k-3$.

By Reciprocity $(5/13)=(13/5)=(8/5)$.

But $(8/5)=(2/5)^3$, and $(2/5)=-1$.

Multiply. We have $4$ $-1$'s, and therefore $(13/257)=1$.

We could alternately use low-tech methods, by explicitly finding an $x$ such that $x^2\equiv 13\pmod{257}$. Not pleasant!

share|improve this answer
    
But we could use high-tech methods to explicitly find $x$. –  Phira Dec 5 '12 at 2:25
    
Or you could just use a spreadsheet, fill a column with 1 through 256, and fill the next column with $=mod(a1^2,257)$ and sort the data on the squares to see if $13$ is there. I don't know how $high-tech$ that is. –  Ross Millikan Dec 5 '12 at 3:19

$\rm mod\ 257\!:\ 13 \,\equiv\, 13\!-\!257 \,\equiv\, -61\cdot 4 \,\equiv\, 196\cdot 4\,\equiv\,49\cdot 4\cdot 4 \,\equiv\, 28^2\ \ $ (took $\,< 10$ secs mentally)

Remark $\ $ Because of the law of small numbers, such negative twiddling and pulling out small square factors often succeeds for small problems.

share|improve this answer

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.