20120426, 17:03  #1 
Aug 2002
Buenos Aires, Argentina
2×3^{2}×83 Posts 
Quadratic residue mod 2^p1
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. 
20120426, 17:31  #2 
Romulan Interpreter
"name field"
Jun 2011
Thailand
19×541 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).

20120426, 17:32  #3  
"Robert Gerbicz"
Oct 2005
Hungary
3113_{8} Posts 
Quote:


20120426, 17:35  #4  
Aug 2002
Buenos Aires, Argentina
2·3^{2}·83 Posts 
Quote:


20120427, 02:41  #5  
"Gang aft agley"
Sep 2002
111010101010_{2} Posts 
Quote:
Quote:
Quote:
Quote:
Last fiddled with by only_human on 20120427 at 02:44 

20120427, 04:13  #6 
May 2003
3013_{8} 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.)

20120427, 05:28  #7  
Romulan Interpreter
"name field"
Jun 2011
Thailand
19·541 Posts 
Quote:
@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^91, 25, 49, 81, etc (all squares are 1 mod 4) or 125, 2197 (all perfect powers of 4k+1 numbers). Nontrivial examples include 57 which is odd and QR of 2^571, 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. 

20120427, 10:36  #8  
"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 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^{2} 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^{2} mod (2^{p} 1) will always be exactly p^{2}: The modulus operation doesn't change it From 5 on, p^{2} 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 nonresidue. So the given example: Quote:
Quote:
Last fiddled with by only_human on 20120427 at 11:15 

20120427, 11:32  #9  
Aug 2002
Buenos Aires, Argentina
2·3^{2}·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 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. Quote:
Last fiddled with by alpertron on 20120427 at 11:38 

20120427, 11:36  #10  
Romulan Interpreter
"name field"
Jun 2011
Thailand
19×541 Posts 
Quote:
19^2=361 is QR (mod 2^{19}1). But 19 is NOT, more exactly, 19 is QNR (mod 2^{19}1). He showed that p is QR, and NOT that p^{2} is QR. 

20120427, 12:52  #11 
"Gang aft agley"
Sep 2002
2×1,877 Posts 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Residue and Shift, what do these mean?  king  Information & Answers  1  20180305 05:52 
Quick! Guess what the next LL residue will be!  NBtarheel_33  Lounge  10  20140314 19:14 
Residue classes  CRGreathouse  Math  4  20090312 16:00 
Can LL residue hit zero before the last iteration?  JuanTutors  Math  3  20040801 19:07 
Masked residue  schneelocke  PrimeNet  6  20031122 01:26 