mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Miscellaneous Math

Reply
 
Thread Tools
Old 2012-04-26, 17:03   #1
alpertron
 
alpertron's Avatar
 
Aug 2002
Buenos Aires, Argentina

2·3·241 Posts
Default Quadratic residue mod 2^p-1

Maybe this is already known, but I could not find it searching on Internet.

Let p>=3 be a prime number. I will show that p is a quadratic residue mod 2p-1 if and only if p=1 (mod 4). It does not matter whether 2p-1 is prime or not.

I will use the following property of the Jacobi symbol (copied from Wikipedia):

\left(\frac{m}{n}\right) <br />
= \left(\frac{n}{m}\right)(-1)^{\frac{m-1}{2}\;\frac{n-1}{2}} =<br />
\begin{cases}<br />
  \;\;\;\left(\frac{n}{m}\right) & \text{if }n \equiv 1 \pmod 4 \text{ or } m \equiv 1 \pmod 4 \\<br />
 -\left(\frac{n}{m}\right) & \text{if }n\equiv m \equiv 3 \pmod 4<br />
\end{cases}

This number p is a quadratic residue mod 2p-1 if it is a quadratic residue mod all their prime factors 2kp+1.

We will compute the Jacobi symbol \left(\frac{p}{2kp+1}\right)

There are two cases p = 1 (mod 4) and p = 3 (mod 4).

\left(\frac{p}{2kp+1}\right)\;=\;\left(\frac{2kp+1}{p}\right)\;=\;\left(\frac{1}{p}\right)\;=\;1

The first equal sign is valid because p = 1 (mod 4).

Since p is a quadratic residue mod all prime factors of 2p-1, we obtain that p is a quadratic residue mod 2p-1.

In the second case, since 2p-1 = 3 (mod 4), at least one of the factors is also congruent to 3 (mod 4). Let this factor be 2kp+1.

\left(\frac{p}{2kp+1}\right)\;=\;-\left(\frac{2kp+1}{p}\right)\;=\;-\left(\frac{1}{p}\right)\;=\;-1

The first equal sign is valid because both p = 3 and 2kp+1 = 3 (mod 4).

So p is not a quadratic residue mod this prime factor of 2p-1, hence it is not a quadratic residue of 2p-1.
alpertron is offline   Reply With Quote
Old 2012-04-26, 17:31   #2
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
"name field"
Jun 2011
Thailand

2·17·293 Posts
Default

As a first observation, I think the Jacobi symbol is in fact the Legendre symbol, as both p and 2kp+1 are primes. The second observation would be that the only place where "p is prime" is used is in the form of the factors, so the question is wouldn't the demonstration work for all odd p, prime or not? (in that case we need to use the Jacobi, of course).
LaurV is offline   Reply With Quote
Old 2012-04-26, 17:32   #3
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

25×72 Posts
Default

Quote:
Originally Posted by alpertron View Post
Maybe this is already known, but I could not find it searching on Internet.
It can be new, though it is totally trivial. And you can also use http://en.wikipedia.org/wiki/Legendre_symbol, don't need the generalization of this.
R. Gerbicz is offline   Reply With Quote
Old 2012-04-26, 17:35   #4
alpertron
 
alpertron's Avatar
 
Aug 2002
Buenos Aires, Argentina

2×3×241 Posts
Default

Quote:
Originally Posted by LaurV View Post
As a first observation, I think the Jacobi symbol is in fact the Legendre symbol, as both p and 2kp+1 are primes. The second observation would be that the only place where "p is prime" is used is in the form of the factors, so the question is wouldn't the demonstration work for all odd p, prime or not? (in that case we need to use the Jacobi, of course).
The problem when p is not prime is that the factors of 2p-1 do not have the form 2kp+1, so the proof does not work.
alpertron is offline   Reply With Quote
Old 2012-04-27, 02:41   #5
only_human
 
only_human's Avatar
 
"Gang aft agley"
Sep 2002

EAA16 Posts
Default

Quote:
Originally Posted by alpertron View Post
Maybe this is already known, but I could not find it searching on Internet.
Considering the caliber of the source *and* the subforum: Gentlemen we are being trolled.
Quote:
I will use the following property of the Jacobi symbol (copied from Wikipedia):
That is clue number two. As a brief aside, is it just my opinion or do others agree that the quality of mathematical articles on Wikipedia is really good nowadays?
Quote:
In the second case, since 2p-1 = 3 (mod 4), at least one of the factors is also congruent to 3 (mod 4). [ ... ]
So p is not a quadratic residue mod this prime factor of 2p-1, hence it is not a quadratic residue of 2p-1.
Now, being the noob that I am, I really don't know what it means if more than one of the factors is 3 (mod 4). Is this the Quadratic residuosity problem?
Quote:
Originally Posted by alpertron View Post
The problem when p is not prime is that the factors of 2p-1 do not have the form 2kp+1, so the proof does not work.
I can't help but think that framing the problem thus, is to be working in a cyclic group, and those here with real math chops are snickering up their sleeves at the obviousness of it all.

Last fiddled with by only_human on 2012-04-27 at 02:44
only_human is offline   Reply With Quote
Old 2012-04-27, 04:13   #6
Zeta-Flux
 
Zeta-Flux's Avatar
 
May 2003

7·13·17 Posts
Default

I'm posting this in haste (always a bad idea) but if I'm remembering correctly, the Jacobi symbol is not the quadratic residue for nonprimes. (If you get -1, then it certainly is not a quadratic residue, but if you get +1 it may still be a nonresidue.)
Zeta-Flux is offline   Reply With Quote
Old 2012-04-27, 05:28   #7
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
"name field"
Jun 2011
Thailand

2×17×293 Posts
Default

Quote:
Originally Posted by only_human View Post
Not really. I think the key here is the fact that they are always in an odd number (the factors which are 7 mod 8). You can always pair them conveniently.

@alpertron: "form of the factor"
That is what I said, the thing "p is prime" is used only in the form of the factors, and therefore it affects only one direction.

You can definitively say:
(1). if p is prime and 1 (mod 4), then p is QR (mod 2p-1)
(2). if p is odd and it is QR (mod 2p-1), then p is (1 mod 4)

For (2), there is nothing about primality of p. Trivial examples include 9 is QR mod 2^9-1, 25, 49, 81, etc (all squares are 1 mod 4) or 125, 2197 (all perfect powers of 4k+1 numbers). Non-trivial examples include 57 which is odd and QR of 2^57-1, but is not prime (the smallest odd composites with this property, which are not perfect powers are: 57, 93, etc).

Otoh, the primality can not be ignored for (1), examples of composites 1 mod 4 which are not QR are: 21, 33, 39, 45, 65, 69, 77, etc.
LaurV is offline   Reply With Quote
Old 2012-04-27, 10:36   #8
only_human
 
only_human's Avatar
 
"Gang aft agley"
Sep 2002

375410 Posts
Default

Ok, first of all
Let me use:
p for the prime >=3
q for factors of 2p-1,


So q = factor of 2p-1 is 2kp+1, so it is always 1 (mod p)
So trivially p and q are relatively prime.
i.e. gcd(p,q) = 1
Also GCD(p, 2p-1) = 1

Since p, any q, and 2p-1, are all relatively prime they can all be used in modular arithmetic nicely with any one of them being the modulus.

Now -- the part where I feel stupid:
for any p>=5, p2 is less than 2p -1
so all these p's will be QRs: 2p -1 is so much bigger that it doesn't ever lop anything off when doing a mod.
That is p2 mod (2p -1) will always be exactly p2:
The modulus operation doesn't change it
From 5 on, p2 can never exceed 2p-1

So now I've said it. These all look like QRs to me. And boy do I feel that I am missing the point.

Edit:
Hey! THAT is the point! Only 3 is a quadratic non-residue. So the given example:
Quote:
In the second case, since 2p-1 = 3 (mod 4), at least one of the factors is also congruent to 3 (mod 4). Let this factor be 2kp+1.
NR only when p is 3
Quote:
both p = 3 and 2kp+1 = 3 (mod 4)
Or am I even more wrong now?

Last fiddled with by only_human on 2012-04-27 at 11:15
only_human is offline   Reply With Quote
Old 2012-04-27, 11:32   #9
alpertron
 
alpertron's Avatar
 
Aug 2002
Buenos Aires, Argentina

26468 Posts
Default

A number is a quadratic residue mod another number if it is a quadratic residue mod all prime factors of the second number. I showed that a prime p = 1 (mod 4) is a quadratic residue mod all prime factors of 2p-1 (which have the form 2kp+1), so it is a quadratic residue mod 2p-1.

When the prime has the form p = 3 (mod 4), I showed that it is not a quadratic residue mod a factor of 2p-1 which is congruent to 3 (mod 4), so p is not a quadratic residue mod 2p-1.

Quote:
Originally Posted by LaurV View Post
@alpertron: "form of the factor"
That is what I said, the thing "p is prime" is used only in the form of the factors, and therefore it affects only one direction.

You can definitively say:
(1). if p is prime and 1 (mod 4), then p is QR (mod 2p-1)
(2). if p is odd and it is QR (mod 2p-1), then p is (1 mod 4)
But in the proof I am not using composite values of p. So I do not see how (2) follows.

Last fiddled with by alpertron on 2012-04-27 at 11:38
alpertron is offline   Reply With Quote
Old 2012-04-27, 11:36   #10
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
"name field"
Jun 2011
Thailand

2·17·293 Posts
Default

Quote:
Originally Posted by only_human View Post
for any p>=5, p2 is less than 2p -1
so all these p's will be QRs: 2p -1 is so much bigger that it doesn't ever lop anything off when doing a mod.
Why you bring p2 here? Of course, p2 is QR in a very trivial sense, for any bigger mod. But p2 is QR, has nothing to do with p is QR. Most of the time it p is not QR in this case.

19^2=361 is QR (mod 219-1).
But 19 is NOT, more exactly, 19 is QNR (mod 219-1).

He showed that p is QR, and NOT that p2 is QR.
LaurV is offline   Reply With Quote
Old 2012-04-27, 12:52   #11
only_human
 
only_human's Avatar
 
"Gang aft agley"
Sep 2002

2·1,877 Posts
Default

Quote:
Originally Posted by only_human View Post
Since p, any q, and 2p-1, are all relatively prime
I got that wrong, of course, q is never relatively prime to 2p-1 because I defined q as a factor of 2p-1
only_human is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Residue and Shift, what do these mean? king Information & Answers 1 2018-03-05 05:52
Quick! Guess what the next LL residue will be! NBtarheel_33 Lounge 10 2014-03-14 19:14
Residue classes CRGreathouse Math 4 2009-03-12 16:00
Can LL residue hit zero before the last iteration? JuanTutors Math 3 2004-08-01 19:07
Masked residue schneelocke PrimeNet 6 2003-11-22 01:26

All times are UTC. The time now is 20:11.


Fri May 20 20:11:17 UTC 2022 up 36 days, 18:12, 0 users, load averages: 1.58, 1.73, 1.75

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.

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