mersenneforum.org  

Go Back   mersenneforum.org > Math Stuff > Other Mathematical Topics

Reply
 
Thread Tools
Old 2020-02-01, 18:44   #1
mgb
 
"Michael"
Aug 2006
Usually at home

5016 Posts
Default 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
mgb is offline   Reply With Quote
Old 2020-02-02, 01:34   #2
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

332110 Posts
Default

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
Dr Sardonicus is offline   Reply With Quote
Old 2020-02-02, 20:24   #3
mgb
 
"Michael"
Aug 2006
Usually at home

24·5 Posts
Default

Quote:
Originally Posted by Dr Sardonicus View Post
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
mgb is offline   Reply With Quote
Reply

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

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

Fri Aug 7 22:27:51 UTC 2020 up 21 days, 18:14, 1 user, load averages: 1.84, 1.95, 1.94

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.