 mersenneforum.org Quadratic residue mod 2^p-1
 Register FAQ Search Today's Posts Mark Forums Read  2012-04-26, 17:03 #1 alpertron   Aug 2002 Buenos Aires, Argentina 2·32·83 Posts 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): 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 There are two cases p = 1 (mod 4) and p = 3 (mod 4). 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. 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.   2012-04-26, 17:31 #2 LaurV Romulan Interpreter   "name field" Jun 2011 Thailand 2·11·467 Posts 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).   2012-04-26, 17:32   #3
R. Gerbicz

"Robert Gerbicz"
Oct 2005
Hungary

32·179 Posts Quote:
 Originally Posted by alpertron 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.   2012-04-26, 17:35   #4
alpertron

Aug 2002
Buenos Aires, Argentina

27268 Posts Quote:
 Originally Posted by LaurV 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.   2012-04-27, 02:41   #5
only_human

"Gang aft agley"
Sep 2002

1110101010102 Posts Quote:
 Originally Posted by alpertron 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 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   2012-04-27, 04:13 #6 Zeta-Flux   May 2003 7·13·17 Posts 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.)   2012-04-27, 05:28   #7
LaurV
Romulan Interpreter

"name field"
Jun 2011
Thailand

240428 Posts Quote:
 Originally Posted by only_human Is this the Quadratic residuosity problem?
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.   2012-04-27, 10:36   #8
only_human

"Gang aft agley"
Sep 2002

2×1,877 Posts 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   2012-04-27, 11:32   #9
alpertron

Aug 2002
Buenos Aires, Argentina

2×32×83 Posts 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 @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   2012-04-27, 11:36   #10
LaurV
Romulan Interpreter

"name field"
Jun 2011
Thailand

282216 Posts Quote:
 Originally Posted by only_human 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.   2012-04-27, 12:52   #11
only_human

"Gang aft agley"
Sep 2002

375410 Posts Quote:
 Originally Posted by only_human 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   Thread Tools Show Printable Version Email this Page Similar Threads Thread Thread Starter Forum Replies Last Post king Information & Answers 1 2018-03-05 05:52 NBtarheel_33 Lounge 10 2014-03-14 19:14 CRGreathouse Math 4 2009-03-12 16:00 JuanTutors Math 3 2004-08-01 19:07 schneelocke PrimeNet 6 2003-11-22 01:26

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

Mon Jan 30 11:52:04 UTC 2023 up 165 days, 9:20, 0 users, load averages: 0.53, 0.68, 0.82