# Is 13 a Quadratic residue of 257?

Is 13 a quadratic residue of 257? Note that 257 is prime.

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

-
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

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!

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

-