Which of the following statements are true?
(1) 73 is a quadratic residue mod 5.
(2) 73 is a quadratic residue mod 83.
(3) 73 is a quadratic residue mod 415.
(4) where is the Jacobi symbol .
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
The point of the problem is to avoid thinking that the answer is (3) and (4).
It's not hard to check that 7 3 is not a quadratic residue mod 5 , and an easy computation with Legendre symbols (and quadratic reciprocity ) shows that it is not a quadratic residue mod 8 3 either: ( 8 3 7 3 ) = ( 7 3 8 3 ) = ( 7 3 1 0 ) = ( 7 3 2 ) ( 7 3 5 ) = ( 7 3 5 ) = ( 5 7 3 ) = ( 5 3 ) = − 1 . (Here we've used that 2 is a square mod an odd prime p if and only if p ≡ ± 1 ( m o d 8 ) , which is the so-called second supplement to quadratic reciprocity.)
So the Jacobi symbol ( 4 1 5 7 3 ) equals the product of ( 5 7 3 ) and ( 8 3 7 3 ) , which is − 1 ⋅ − 1 = 1 . Hence statements (1) and (2) are false and statement (4) is true.
But, unlike the Legendre symbol, the Jacobi symbol being equal to 1 does not imply that 7 3 is a square mod 4 1 5 . Indeed, if x 2 ≡ 7 3 ( m o d 4 1 5 ) , then x 2 ≡ 7 3 ( m o d 5 ) , which is impossible. In fact, the Chinese Remainder Theorem shows that it's a square mod 4 1 5 if and only if it's a square mod 5 and mod 8 3 . So it's not enough that the product of the Legendre symbols is 1 --all the Legendre symbols have to be 1 individually!
This was the first question I was asked as a graduate student during my oral qualifying examination ("is 73 a square mod 415?"); I believe it was asked as a very gentle way to warm me up and calm me down, since it was much easier than the questions that came afterward!