 mersenneforum.org Creating Consecutive Quadratic Residues
 Register FAQ Search Today's Posts Mark Forums Read 2020-02-01, 18:44 #1 mgb   "Michael" Aug 2006 Usually at home 24×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) u2 - v2 = aa-1 = 1 (mod p) u2 = v2 + 1 (mod p) v2 = q1(mod p) v2 + 1 = q2(mod p) q1, q2 are consecutive quadratic residues modulo p To separate q1 and q2 by c > 1, multiply by c That is if (a + a-1c) is even let v = (a - a-1c)/2 v2 = q1(mod p) v2 + c = q2(mod p) so that |q1 - q2| = c Last fiddled with by mgb on 2020-02-01 at 18:44   2020-02-02, 01:34 #2 Dr Sardonicus   Feb 2017 Nowhere 34×41 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-1r - R-1r' = 1. Last fiddled with by Dr Sardonicus on 2020-02-02 at 01:39 Reason: xifnig posty   2020-02-02, 20:24   #3
mgb

"Michael"
Aug 2006
Usually at home

1208 Posts Quote:
 Originally Posted by Dr Sardonicus First: If p is an odd prime, then 2 (mod p) is invertible. It doesn't matter whether a + a-1 is even.
Yes, I noticed that it works for odd sums as well.

Quote:
 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-1r - R-1r' = 1.
Yes, this would be equivalent to writing v = (a - a-1c)/2 as v = (a - a-1R)/2 giving a distance of R between q1 and q2

Many thanks for this information.

Last fiddled with by mgb on 2020-02-02 at 20:26  Thread Tools Show Printable Version Email this Page Similar Threads Thread Thread Starter Forum Replies Last Post LaurV Math 18 2017-09-16 14:47 zippy Math 6 2015-07-20 13:09 smslca Math 0 2012-10-12 06:42 Romulas Math 3 2010-05-09 03:27

All times are UTC. The time now is 22:31.

Fri Aug 7 22:31:09 UTC 2020 up 21 days, 18:17, 1 user, load averages: 2.30, 2.15, 2.02