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.
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.
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!
$\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.
Quadratic reciprocity (QR) is the way to go, but a little ingenuity simplifies the solution.
Start with $(13|257)=(257|13)=(10|13)$. We can't directly apply QR again because $10$ is even. But, since $13$ is a prime one greater than a multiple of $4$, $(10|13)=(-10|13)=(3|13)$. Now we apply QR again: $(3|13)=(13|3)=(1|3)$.
So $(13|257)=(10|13)=(1|3)$. Through a great deal of arduous effort we find that $(1|3)=1$ so $(13|257)=1$ rendering $13$ a quadratic residue $\bmod 257$.