# reformulation of square residues for odd numbers?

you will find that for x^2 mod N where N is odd, we have N different residues but with simetry in half:

Example: N=25

mod 25

1,4,9,16,0,11,24,14,6,0,21,19 left side

19,21,0,6,14,24,11,0,16,9,4,1,0 right side

If we start from number 19 on the right side then difference between other right side numbers and 19 is

0, 2, 6, 12, 20, 30, 42, 56, 72, 90, 110, 132, 156, mod 25 http://oeis.org/A002378

formula for that sequence is n(n+1) or n(n-1)

If we go on with numbers we folow numbers of the left side. Residues of mod 25 is cycle of 25 numbers.

So if we want to find x^2 mod 25 = 14 is this the same as finding solution for (y^2-y+19) mod 25 = 14 ?

example: from the above we get for 5 => (25-5+19) mod 25 = 14. Number five in that case means fifth number from the right sequence x^2 mod 25 which represents square number 289. Next square number with same residue is 16 places further(number 33^2)

-
There are not $N$ different residues; as you point out yourself, many of them are the same. – joriki Aug 25 '12 at 14:12

Yes, they are the same: $y^2 - y + 19$ is the same as $(y-13)^{2}$ (mod $25$), so the answers to one congruence are translates of the answers to the other.
Expand: $-26\equiv -1\pmod{25}$, $169\equiv 19\pmod{25}$. – André Nicolas Aug 25 '12 at 18:39
Or, $(y^2 - 26y + 169) = y^2 - y + 19 -25(y-6).$ – Geoff Robinson Aug 25 '12 at 20:24