20150711, 17:36  #1 
Jul 2015
2 Posts 
quadratic residues
Hi people,
I am wondering about the following: Is anything known about what would be the maximal distance/spacing between two quadratic residues modulo some primorial? Some texts are around for the modulus squarefree, but they are too complicated for me. Does anyone know anything about this? Or maybe if I'm asking this at the wrong forum, could anyone direct me to people knowing more about this? Greet Zippy 
20150711, 22:56  #2  
"Forget I exist"
Jul 2009
Dartmouth NS
2×3×23×61 Posts 
Quote:
using b# as the primorial function up to b: through algebra we can say mod n so for 3# we can say 0^2,1^2,2^2, and 3^2 is all we need to know mod 6 to figure that one out. for 5# if comes down to the gaps in 0^2,1^2,3^2,4^2,5^2,...15^2 some of these wrap around and pass others. we can narrow down the maximum gap by knowing when it wraps around because it wraps around past 0 so the number it wraps around at needs to pass 0 it can only be the largest gap if it exceeds the square of the number two previous to itself and the gap to pass 0 wasn't greater than the gap at the last non wrap around value before it. for example in the 3# list 3^2 wraps around to 3, 3>1 so the gap of 2 until 0 is the largest. in the 5# list we know that 6^2 >30 so we check does it wrap to a number greater than 4^2 if not then we compare 5^24^2 to 305^2 and we see that at least until it wraps around the first time 5^24^2 is the largest except we haven't considered all values up to 15^2 to see if they interfere we know the difference between squares is the number we want to square plus the previous number we square. we need to know if this interferes in this case the slowest way is to check them all okay we have that , keep going adding odd numbers in order starting with 13 ( 6+7) we get so we have the following mod 30: 0,1,4,6,9,10,15,16,19,21,24,25, the biggest gap of 5 happens twice 10,15 and 25,0. I'm crap at math so I can't give you a general way. Last fiddled with by science_man_88 on 20150711 at 22:57 

20150712, 23:20  #3 
(loop (#_fork))
Feb 2006
Cambridge, England
2×7×461 Posts 
Interesting question! There's going to be some contribution based on the smallest pseudosquare (e.g. mod 2*3*5*7*11*13*17*19*23, the first quadratic residue which isn't the lift of a rational square is 399, so there are gaps going up to 37 before that); thinking of it as a collection of independent Bernoulli random variables I'd expect something of the order of 2^{number of primes in product}.
Mod 2*3*5*7*11*13*17*19*23 the biggest gap appears to be the 1157 before 63495366. Code:
N=2*3*5*7*11*13*17;print(N);bsf=0;k=1;for(j=2,N1,if(issquare(Mod(j,N)),if(jk>bsf,bsf=jk;print([jk,j]));k=j)) 
20150714, 00:13  #4 
(loop (#_fork))
Feb 2006
Cambridge, England
1100100110110_{2} Posts 
Apropos of little, the biggest gap for 2*3*5*7*11*13*17*19*23*29 is 2902, coming up to t=787098376.
Is there even a sensible way, beyond exhaustive search over signsofsquareroots, of finding the smallest positive N with N^2 == X mod Y for some Y with lots of prime factors? Code:
q=N;forvec(X=vector(10,t,[0,1]),L=lift(chinese(vector(10,t,(2*X[t]1)*sqrt(Mod(787095474,p[t])))));if(L<q,print(L);q=L)) 
20150717, 11:51  #5 
Just call me Henry
"David"
Sep 2007
Liverpool (GMT/BST)
37×163 Posts 
I can't think of a way to find the smallest. To find an example a possible method would be similar to the quadratic sieve. Whether this could be improved upon for a highly composite number is a different question.

20150717, 13:42  #6  
"Forget I exist"
Jul 2009
Dartmouth NS
2×3×23×61 Posts 
Quote:
Last fiddled with by science_man_88 on 20150717 at 13:49 

20150720, 13:09  #7 
Jul 2015
2 Posts 
hi
Thanks for replying,
I am actually looking at invertible elements modulo an odd primorial, since half of them are shifts of squares I wondered about this. Anyway it seems not an easy question. 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
question: decidability for quadratic residues modulo a composite  LaurV  Math  18  20170916 14:47 
Fun with LL residues  NBtarheel_33  Data  19  20150421 16:02 
residues and non residues of general quadratic congruences  smslca  Math  0  20121012 06:42 
weird residues  ATH  Data  2  20120814 02:25 
Quadratic Residues  Romulas  Math  3  20100509 03:27 