quadratic residues

zippy · 2015-07-11, 17:36

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

science_man_88 · 2015-07-11, 22:56

Quote:

Originally Posted by zippy

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

using b# as the primorial function up to b:

through algebra we can say $a^2 = (n-a)^2$ 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^2-4^2 to 30-5^2 and we see that at least until it wraps around the first time 5^2-4^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 $6^2\eq 6 \pmod {30}$ , keep going adding odd numbers in order starting with 13 ( 6+7) we get $7^2\eq 19 \pmod {30}; 8^2\eq 4 \pmod {30};9^2\eq 21\pmod {30};10^2\eq 10\pmod {30};11^2\eq 1\pmod {30};12^2\eq 24 \pmod {30};13^2\eq 19\pmod {30};14^2\eq 16\pmod {30}; 15^2\eq 15\pmod {30}$ 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.

fivemack · 2015-07-12, 23:20

Interesting question! There's going to be some contribution based on the smallest pseudo-square (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,N-1,if(issquare(Mod(j,N)),if(j-k>bsf,bsf=j-k;print([j-k,j]));k=j))

fivemack · 2015-07-14, 00:13

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 signs-of-square-roots, 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))

henryzz · 2015-07-17, 11:51

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.

science_man_88 · 2015-07-17, 13:42

Quote:

Originally Posted by fivemack

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 signs-of-square-roots, 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))

since we know it repeats we know the upper limit of N is the ceil(Y/2) for odd Y and Y/2 for even Y. we could then say that the maximum number of squares that fit into Y is sqrtint(Y) so it can only go that far before wrapping around each time. it then comes down to the difference between square for when it may hit values as these are of the form sqrtint(Y)*2*b + b^2 really what determines what shift each new group lands is sqrtint(Y)*2*b - the last square to fit in the value each round. the problem really seems to arise for me when I can't determine b until I hit the next wrap around. edit: - (the number minus the last residue to be a square each round).

zippy · 2015-07-20, 13:09

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.

2015-07-11, 17:36	#1
zippy 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

2015-07-12, 23:20	#3
fivemack (loop (#_fork)) Feb 2006 Cambridge, England 2×7×461 Posts	Interesting question! There's going to be some contribution based on the smallest pseudo-square (e.g. mod 23571113171923, 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 23571113171923 the biggest gap appears to be the 1157 before 63495366. Code: N=2357111317;print(N);bsf=0;k=1;for(j=2,N-1,if(issquare(Mod(j,N)),if(j-k>bsf,bsf=j-k;print([j-k,j]));k=j))

2015-07-14, 00:13	#4
fivemack (loop (#_fork)) Feb 2006 Cambridge, England 1100100110110₂ Posts	Apropos of little, the biggest gap for 2357111317192329 is 2902, coming up to t=787098376. Is there even a sensible way, beyond exhaustive search over signs-of-square-roots, 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,(2X[t]-1)*sqrt(Mod(787095474,p[t])))));if(L<q,print(L);q=L))

2015-07-20, 13:09	#7
zippy 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.

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
Fun with LL residues	NBtarheel_33	Data	19	2015-04-21 16:02
residues and non residues of general quadratic congruences	smslca	Math	0	2012-10-12 06:42
weird residues	ATH	Data	2	2012-08-14 02:25
Quadratic Residues	Romulas	Math	3	2010-05-09 03:27

2015-07-17, 11:51	#5
henryzz 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.