# Quadratic Residues, Non-residues and Primitive Roots

Can anyone explain to me what special significance each of these has. I know how to calculate/verify whether a number is one of them relative to a modulus using Euler's criterion, but, for example, what does it mean for a number to be a primitive root modulo $n$?

-
In short, a number $a$ coprime to $n$ is a primitive root modulo $n$ if $a$ generates the unit group $U(\mathbb{Z}/n\mathbb{Z})$, which occurs when $a$ has order $\phi(n)$ in $\mathbb{Z}/n\mathbb{Z}$. – Ben West Jan 23 '13 at 16:26

The idea has come from the Primitive Root of Unity.

We know, if $a$ is $n$-th Primitive Root of Unity, it generates all the roots of $$z^n=1$$

Similarly, if $g$ is a Primitive Root $\pmod m,$ it generates all the natural numbers $<m$ and co-prime with $m$

For example, let $g=2,m=9$

$2^1=2\equiv2\pmod 9,2^2=4\equiv4,2^3=8\equiv8,2^4=16\equiv7,2^5=32\equiv5,2^6=64\equiv1$

So, we have generated $2,4,8,7,5,1$ all the numbers relatively prime to $9$ and less than it. Hence, $2$ is a Primitive Root $\pmod 9$

Proof :

Let $ord_mh=r\implies h^r\equiv1\pmod m$

Let $h^s\equiv1\pmod m$ where $s=q\cdot r+t$ where $0\le t<r$

So, $h^{q\cdot r+t}\equiv1\pmod m\implies h^t(h^r)^q\equiv1\implies h^t\equiv1$

But $r$ is the smallest positive integer such that $h^r\equiv1\pmod m\implies t=0\implies r\mid s$

Now, if $h^b\equiv h^c\pmod m$ where $(h,m)=1$ and $b>c$

$m\mid(h^{b-c}-1)\implies h^{b-c}\equiv1\pmod m\implies r\mid(b-c)$

We know by Euler's Totient Theorem, $h^{\phi(m)}\equiv1\pmod m\implies r\mid\phi(m)$

If $r=\phi(m), h$ is called a Primitive Root $\pmod m$

If $h^b\equiv h^c\pmod m\implies \phi(m)\mid(b-c)$

So, $h^{c_1}\not\equiv h^{c_2}\pmod m$ if $0\le c_1<c_2<\phi(m)$

So, we shall get $\phi(m)$ in-congruent numbers $h^c$ for $0\le c<\phi(m)$

-