$$\newcommand{\id}{\mathrm{id}}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\kernel}{\mathrm{null}\,}$$ $$\newcommand{\range}{\mathrm{range}\,}$$ $$\newcommand{\RealPart}{\mathrm{Re}}$$ $$\newcommand{\ImaginaryPart}{\mathrm{Im}}$$ $$\newcommand{\Argument}{\mathrm{Arg}}$$ $$\newcommand{\norm}[1]{\| #1 \|}$$ $$\newcommand{\inner}[2]{\langle #1, #2 \rangle}$$ $$\newcommand{\Span}{\mathrm{span}}$$

# 5: Primitive Roots and Quadratic Residues

[ "article:topic-guide", "authorname:wraji" ]

$$\newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} }$$

$$\newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}}$$

In this chapter, we discuss the multiplicative structure of the integers modulo $$n$$. We introduce the concept of the order of integer modulo $$n$$ and then we study its properties. We then define primitive roots modulo $$n$$ and show how to determine whether an integer is primitive modulo $$n$$ or not. We later find all positive integers having primitive roots and prove related results. We define the concept of a quadratic residue and establish its basic properties. We then introduce Legendre symbol and also develop its basic properties. We also introduce the law of quadratic reciprocity. Afterwards, we generalize the notion of Legendre symbol to the Jacobi symbol and discuss the law of reciprocity related to Jacobi symbol.

### Contributors

• Dr. Wissam Raji, Ph.D., of the American University in Beirut. His work was selected by the Saylor Foundation’s Open Textbook Challenge for public release under a Creative Commons Attribution (CC BY) license.