I think I must be doing something wrong (either that or I'm not keeping track of my calculation correctly). I'm trying to get used to using Euler's criterion , i.e. that $a$ is a quadratic residue of $p$ if and only if $a^{p-1/2}\equiv1\mod p$. I keep getting non $\pm1$ numbers, so I know I'm making a mistake.
Say we want to see if $31$ is a quadratic residue of $71$, here's how I've been trying to do it (I know I should add in $\bmod71$ in the following but take it for granted that every calculation is $\bmod71$)
$31^{(71-1)/2}\equiv31^{35}\equiv (31^2)^{16}31^3\equiv (38)^{16}31^3\equiv(38)^831^3\equiv(24)^831^3\equiv (24^2)^431^3\equiv (58)^431^3\equiv(58^2)^231^3\equiv6^231^3\equiv36.31^3\equiv30\equiv69.31\equiv9\mod71$
Can anyone please tell me what I'm doing wrong ??
Calculating it the long way ... $$31^{35}\equiv(31^5)^7\equiv 34^7\equiv -1\pmod{71}$$ Okay yes, I used more intermediate steps than that. But, you use the same style trick later in your sequence. $38^2\equiv 24 \bmod 71$ for the 2,8 reduction steps, $24^2\equiv 8\bmod 71$ for the 2,4 reduction , $8^2\equiv 64\bmod 71$ in the 2,2 reduction, $64^2\equiv 49\bmod 71$ so $49(42)\equiv -1\bmod 71$ I had to correct myself, several times, to write it out.