Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

If you look at the table of square residues: http://en.wikipedia.org/wiki/Quadratic_residue#Table_of_quadratic_residues

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)

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

1 Answer 1

up vote 2 down vote accepted

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.

share|improve this answer
    
Can you explain how it is the same for (y-13)^2. Thanks –  Bojan Vasiljević Aug 25 '12 at 17:29
2  
Expand: $-26\equiv -1\pmod{25}$, $169\equiv 19\pmod{25}$. –  André Nicolas Aug 25 '12 at 18:39
1  
Or, $(y^2 - 26y + 169) = y^2 - y + 19 -25(y-6).$ –  Geoff Robinson Aug 25 '12 at 20:24

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.