Quadratic residue mod 2^p-1

[alpertron]

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 2^p-1 if and only if p=1 (mod 4). It does not matter whether 2^p-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 2^p-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 2^p-1, we obtain that p is a quadratic residue mod 2^p-1.

In the second case, since 2^p-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 2^p-1, hence it is not a quadratic residue of 2^p-1.

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

[R. Gerbicz]

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.

[alpertron]

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 2^p-1 do not have the form 2kp+1, so the proof does not work.

[only_human]

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.

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?

In the second case, since 2^p-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 2^p-1, hence it is not a quadratic residue of 2^p-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?

Originally Posted by alpertron

The problem when p is not prime is that the factors of 2^p-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.

[Zeta-Flux]

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

[LaurV]

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 2^p-1)
(2). if p is odd and it is QR (mod 2^p-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.

[only_human]

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


So q = factor of 2^p-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, 2^p-1) = 1

Since p, any q, and 2^p-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, p² is less than 2^p -1
so all these p's will be QRs: 2^p -1 is so much bigger that it doesn't ever lop anything off when doing a mod.
That is p² mod (2^p -1) will always be exactly p²:
The modulus operation doesn't change it
From 5 on, p² can never exceed 2^p-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:

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

both p = 3 and 2kp+1 = 3 (mod 4)

Or am I even more wrong now?

[alpertron]

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 2^p-1 (which have the form 2kp+1), so it is a quadratic residue mod 2^p-1.

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

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 2^p-1)
(2). if p is odd and it is QR (mod 2^p-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.

[LaurV]

Originally Posted by only_human

for any p>=5, p² is less than 2^p -1
so all these p's will be QRs: 2^p -1 is so much bigger that it doesn't ever lop anything off when doing a mod.

Why you bring p² here? Of course, p² is QR in a very trivial sense, for any bigger mod. But p² 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 2¹⁹-1).
But 19 is NOT, more exactly, 19 is QNR (mod 2¹⁹-1).

He showed that p is QR, and NOT that p² is QR.

[only_human]

Originally Posted by only_human

Since p, any q, and 2^p-1, are all relatively prime

I got that wrong, of course, q is never relatively prime to 2^p-1 because I defined q as a factor of 2^p-1