1
$\begingroup$

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.

  • 0
    For absolute confidence that the answer is yes, $28^2 = 784 = 3\cdot 257 + 13$2018-04-17

3 Answers 3

7

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!

  • 0
    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.2012-12-05
5

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

1

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