Register FAQ Search Today's Posts Mark Forums Read

2015-07-11, 22:56   #2
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

839110 Posts

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.

Last fiddled with by science_man_88 on 2015-07-11 at 22:57

 2015-07-12, 23:20 #3 fivemack (loop (#_fork))     Feb 2006 Cambridge, England 11001001101102 Posts 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))
 2015-07-14, 00:13 #4 fivemack (loop (#_fork))     Feb 2006 Cambridge, England 2·7·461 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 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
 2015-07-17, 11:51 #5 henryzz Just call me Henry     "David" Sep 2007 Liverpool (GMT/BST) 10111011010002 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.
2015-07-17, 13:42   #6
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

3·2,797 Posts

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
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).

Last fiddled with by science_man_88 on 2015-07-17 at 13:49

 2015-07-20, 13:09 #7 zippy   Jul 2015 210 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 LaurV Math 18 2017-09-16 14:47 NBtarheel_33 Data 19 2015-04-21 16:02 smslca Math 0 2012-10-12 06:42 ATH Data 2 2012-08-14 02:25 Romulas Math 3 2010-05-09 03:27

All times are UTC. The time now is 19:13.

Mon Aug 15 19:13:25 UTC 2022 up 39 days, 14 hrs, 1 user, load averages: 1.43, 1.47, 1.40