mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2015-07-11, 17:36   #1
zippy
 
Jul 2015

2 Posts
Default 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
zippy is offline   Reply With Quote
Old 2015-07-11, 22:56   #2
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

3×2,797 Posts
Default

Quote:
Originally Posted by zippy View Post
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
science_man_88 is offline   Reply With Quote
Old 2015-07-12, 23:20   #3
fivemack
(loop (#_fork))
 
fivemack's Avatar
 
Feb 2006
Cambridge, England

11001001101102 Posts
Default

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 is offline   Reply With Quote
Old 2015-07-14, 00:13   #4
fivemack
(loop (#_fork))
 
fivemack's Avatar
 
Feb 2006
Cambridge, England

2×7×461 Posts
Default

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))
fivemack is offline   Reply With Quote
Old 2015-07-17, 11:51   #5
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Liverpool (GMT/BST)

23·7·107 Posts
Default

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.
henryzz is offline   Reply With Quote
Old 2015-07-17, 13:42   #6
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

100000110001112 Posts
Default

Quote:
Originally Posted by fivemack View Post
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).

Last fiddled with by science_man_88 on 2015-07-17 at 13:49
science_man_88 is offline   Reply With Quote
Old 2015-07-20, 13:09   #7
zippy
 
Jul 2015

216 Posts
Default 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.
zippy 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
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

All times are UTC. The time now is 02:33.


Thu Aug 18 02:33:02 UTC 2022 up 1 min, 0 users, load averages: 1.53, 0.39, 0.14

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2022, 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.

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎𝜍 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔