Content deleted Content added
Ltypestar2 (talk | contribs) m grammer fix |
→Sieve improvement: Added quadratic residue link. Tags: Mobile edit Mobile app edit Android app edit App select source |
||
Line 107:
|}
It is not necessary to compute all the square-roots of <math>a^2-N</math>, nor even examine all the values for {{mvar|a}}. Squares are always congruent to 0, 1, 4, 5, 9, 16 [[Modular arithmetic|modulo]] 20, because these are the [[quadratic residue]]s of 20. The values repeat with each increase of {{mvar|a}} by 10. In this example, N is 17 mod 20, so subtracting 17 mod 20 (or adding 3), <math>a^2-N</math> produces 3, 4, 7, 8, 12, and 19 modulo 20 for these values. It is apparent that only the 4 from this list can be a square. Thus, <math>a^2</math> must be 1 mod 20, which means that {{mvar|a}} is 1, 9, 11 or 19 mod 20; it will produce a <math>b^2</math> which ends in 4 mod 20 and, if square, {{mvar|b}} will end in 2 or 8 mod 10.
This can be performed with any modulus. Using the same <math>N=2345678917</math>,
| |||