219 is a quadratic residue modulo 383?

## - Exercise solutions -

## - Solution of exercises -
By the multiplicativity of the Legendre symbol, we have $\left(\frac{219}{384}\right)=\left(\frac{3}{383}\right)\left(\frac{7}{383}\right)$. By two applications of the quadratic reciprocity law, we deduce that $\left(\frac{219}{383}\right)=-\left(\frac{383}{3}\right)\left(\frac{383}{73}\right)$. Then, by reducing modulo 3 and 73 respectively, $\left(\frac{219}{383}\right)=-\left(\frac{-1}{3}\right)\left(\frac{18}{73}\right)=\left(\frac{18}{73}\right)$. Once again by multiplicativity, we have $\left(\frac{219}{383}\right)=\left(\frac{2}{73}\right)\left(\frac{3}{73}\right)^{2}=\left(\frac{2}{73}\right)$, and by Proposition 59, we finally deduce that $\left(\frac{2}{73}\right)=1$, so 219 is a quadratic residue modulo

383.

## 2 Second Course/TD

## - Primitive Root -

Let $n>1$ and $a$ be coprime with $n$. In the first course, you have seen $\omega_{n}(a)$, the order of $a$ modulo $n$, and you know that this order is a divisor of $\varphi(n)$. Here we will look for elements whose order is exactly $\varphi(n)$. In the rest of this course, we will denote $(\mathbb{Z} / n \mathbb{Z})^{*}$ the set of elements of $\mathbb{Z} / n \mathbb{Z}$ that are invertible (i.e., coprime with $n$).

Definition 60. Let $n$ be an integer and $x$ coprime with $n$. We say that $x$ is a primitive root modulo $n$ if the order of $x$ is $\varphi(n)$.

Definition 61. Let $n$ be