Quadratic residues and composite moduli

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) ( 73 415 ) = 1 , \left( \dfrac{73}{415} \right) = 1, where ( a n ) \left( \dfrac{a}{n} \right) is the Jacobi symbol .

(1), (2), (3), (4) (2) only (2) and (4) (3) and (4) (4) only

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.

1 solution

Patrick Corn
Apr 3, 2017

The point of the problem is to avoid thinking that the answer is (3) and (4).

It's not hard to check that 73 73 is not a quadratic residue mod 5 , 5, and an easy computation with Legendre symbols (and quadratic reciprocity ) shows that it is not a quadratic residue mod 83 83 either: ( 73 83 ) = ( 83 73 ) = ( 10 73 ) = ( 2 73 ) ( 5 73 ) = ( 5 73 ) = ( 73 5 ) = ( 3 5 ) = 1. \begin{aligned} \left( \frac{73}{83} \right) &= \left( \frac{83}{73} \right) \\ &= \left( \frac{10}{73} \right) \\ &= \left( \frac{2}{73} \right) \left( \frac{5}{73} \right) \\ &= \left( \frac{5}{73} \right) \\ &= \left( \frac{73}{5} \right) \\ &= \left( \frac35 \right) = -1. \end{aligned} (Here we've used that 2 2 is a square mod an odd prime p p if and only if p ± 1 ( m o d 8 ) , p \equiv \pm 1 \pmod 8, which is the so-called second supplement to quadratic reciprocity.)

So the Jacobi symbol ( 73 415 ) \left( \dfrac{73}{415} \right) equals the product of ( 73 5 ) \left( \dfrac{73}{5} \right) and ( 73 83 ) , \left( \dfrac{73}{83} \right), which is 1 1 = 1. -1 \cdot -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 1 does not imply that 73 73 is a square mod 415. 415. Indeed, if x 2 73 ( m o d 415 ) , x^2 \equiv 73 \pmod{415}, then x 2 73 ( m o d 5 ) , x^2 \equiv 73 \pmod 5, which is impossible. In fact, the Chinese Remainder Theorem shows that it's a square mod 415 415 if and only if it's a square mod 5 5 and mod 83. 83. So it's not enough that the product of the Legendre symbols is 1 1 --all the Legendre symbols have to be 1 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!

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...