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, 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

 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