2020-02-01, 18:44 | #1 |
"Michael"
Aug 2006
Usually at home
2^{4}·5 Posts |
Creating Consecutive Quadratic Residues
While working on another problem I stumbled across this if anyone has a use for it.
To create all consecutive quadratic residues modulo p, p an odd prime. For all a < p find a^{-1}(mod p) If (a + a^{-1}) is even let v = (a - a^{-1})/2 u = (a + a^{-1})/2 u - v = a and u + v = a^{-1} (or vise versa) u^{2} - v^{2} = aa^{-1} = 1 (mod p) u^{2} = v^{2} + 1 (mod p) v^{2} = q_{1}(mod p) v^{2} + 1 = q_{2}(mod p) q_{1}, q_{2} are consecutive quadratic residues modulo p To separate q_{1} and q_{2} by c > 1, multiply by c That is if (a + a^{-1}c) is even let v = (a - a^{-1}c)/2 v^{2} = q_{1}(mod p) v^{2} + c = q_{2}(mod p) so that |q_{1} - q_{2}| = c Last fiddled with by mgb on 2020-02-01 at 18:44 |
2020-02-02, 01:34 | #2 |
Feb 2017
Nowhere
2×23×71 Posts |
First: If p is an odd prime, then 2 (mod p) is invertible. It doesn't matter whether a + a^{-1} is even.
Second: This formulation gives an elementary way of counting the number of pairs of consecutive quadratic residues (mod p). The number of pairs of inverse elements (a, a^{-1}) with 0 < a <= a^{-1} < p is (p+1)/2 (the elements 1 and p-1 are self-inverse). If p == 3 (mod 4), a + a^{-1} is never 0, so the pairs may be grouped in pairs of opposites, (a, a^{-1}) with (p - a^{-1}, p - a). Selecting one member of each such pair, we obtain (p+1)/4 quadratic residues ((a + a^{-1})/2)^2 (mod p) for which r - 1 = ((a - a^{-1})/2)^2 is also a quadratic residue. One of these is r = 1 (a = 1). If p == 3 (mod 4), then, there are (p - 3)/4 pairs of consecutive nonzero quadratic residues r-1, r. If p == 1 (mod 4), the quadratic residue -1 (mod p) affects the count. The (p+1)/2 pairs of inverse elements include one pair of inverse elements whose sum is 0 -- the two square roots of -1 (mod p). So we obtain (p-3)/4 pairings (a, a^{-1}) with (p - a^{-1}, p - a), and the "odd man out" pair of inverse elements whose sum is 0. The (p-3)/3 pairings again give the residue r = 1 with r - 1 = 0; the "odd man out" pair gives the residue r = 0, with r-1 = -1 (mod p). If p == 1 (mod 4), then, there are (p-5)/4 consecutive pairs r-1, r of nonzero quadratic residues. If p = 7, the pair 1, 2 is the only pair of consecutive nonzero quadratic residues. If p > 7, the following (which I did not invent) gives at least one pair: The squares 1, 4, and 9 are quadratic residues (mod p). If either 2 or 5 is a quadratic residue (mod p) then either 1, 2 or 4, 5 is a pair of consecutive nonzero quadratic residues. If neither 2 nor 5 is a quadratic residue, then 2*5 = 10 is a quadratic residue, so 9, 10 is a pair of consecutive nonzero quadratic residues. Also note: If R is a nonzero quadratic residue (mod p), the number of pairs of quadratic residues r, r' for which r - r' = R is the same as the number of consecutive pairs of quadratic residues. For each such pair, we have correspondingly R^{-1}r - R^{-1}r' = 1. Last fiddled with by Dr Sardonicus on 2020-02-02 at 01:39 Reason: xifnig posty |
2020-02-02, 20:24 | #3 | ||
"Michael"
Aug 2006
Usually at home
2^{4}·5 Posts |
Quote:
Quote:
Many thanks for this information. Last fiddled with by mgb on 2020-02-02 at 20:26 |
||
Thread Tools | |
Similar Threads | ||||
Thread | Thread Starter | Forum | Replies | Last Post |
question: decidability for quadratic residues modulo a composite | LaurV | Math | 18 | 2017-09-16 14:47 |
quadratic residues | zippy | Math | 6 | 2015-07-20 13:09 |
residues and non residues of general quadratic congruences | smslca | Math | 0 | 2012-10-12 06:42 |
Quadratic Residues | Romulas | Math | 3 | 2010-05-09 03:27 |