# Proving there are no primitive roots of $2009$

We know that $2009=7^2*41$ and that $\phi(2009)=1680$ and by the Fermat-Euler theorem we have that for every $a$ coprime to 2009: $a^{1680}=1 \pmod{2009}$ and I get stuck here, I tried using Jacobi symbols but I kinda get nowhere with that, I'd appreciate any help!

-

There is a theorem which states that there exists primitive roots modulo $n$ if and only if $n$ equals $2,4,p^k,2p^k$ where $p$ is an odd prime number.

To understand better this particular case, the essential problem is that $\phi(7^2)=6*7$ and $\phi(41)=40$, both of which have a factor of $2$. In terms of groups, the multiplicative group will be isomorphic to $$\mathbb{Z}/7\mathbb{Z}\times \mathbb{Z}/5\mathbb{Z}\times \mathbb{Z}/3\mathbb{Z}\times \mathbb{Z}/8\mathbb{Z}\times \mathbb{Z}/2\mathbb{Z},$$ so that taking a power of $8$ kills that part of the group. In other words, for any $a$ relatively prime to $2009$, $$a^{840}\equiv 1 \pmod {2009}.$$

For a concrete solution, let $a$ be an $8^{th}$ root of $1$ modulo $2009$, and calculate the Jacobi Symbol of $a$ over $2009$. This Jacobi symbol will be $-1$, which implies that there are no primitive roots.

-
"This Jacobi symbol will be −1, which implies that there are no primitive roots" I f a is a quardic resiude then Jacobi symbol will be 1, But if Jacobi symbol is 1 then is not neccesery quardic resiude ->not neccesery no primitive roots. Am I right? –  user1932595 Apr 4 '13 at 6:32

Using Carmichael Function, $\lambda(2009)=$lcm$(\lambda(7^2),\lambda(41))=$lcm$(7(7-1),40)=2\cdot20\cdot21=840$

So, if $(a,2009)=1, a^{840}\equiv1\pmod{2009}\implies ord_{2009}a\mid840$

So, there is no integer $a$ such that $ord_{2009}a=\phi(2009)=\phi(41)\phi(7^2)=40\cdot7\cdot(7-1)=1680$, hence there is no primitive root.

-

By a theorem by Gauss (I think), there are no primitive roots modulo $r s$ if $r$ and $s$ are relatively prime and both greater than 2. We have that $\phi(r)$ and $\phi(s)$ have at least the factor 2 in common, so by Euler's theorem we can write for $a$ relatively prime to $r s$: $$a^{\phi(r s) / 2} \equiv \left( a^{\phi(r)} \right)^{\phi(s) / 2} \equiv 1 \pmod{r}$$ The same for $s$, so $a$ doesn't have order $\phi(r s)$, and there are no primitive roots.

-

We Have $\phi(2009)=7^2*41$ lets assume a is a primitive root of 2009 and so we get $a^{1680}=1 \pmod{2009}$ but by the Fermat-Eeluer Theorem we have $a^{42}=1 \pmod{49}$ and $a^{40}=1 \pmod{41}$

and so we finally have $a^{lcm(42,40)}=1 \pmod {49*41=2009}$ but because $gcd(40,42)=2$ then $lcm(42,40)<42*40$ and then a is not a primitive root by contradiction.

-

By the Chinese Remainder Theorem, $U_{2009} \cong U_{41} \times U_{49}$.

By Euler–Fermat, $40$ is an exponent of $U_{41}$ and $42$ is an exponent of $U_{49}$.

Hence, $840=\mbox{lcm}(40,42)$ is an exponent of $U_{2009}$, but $U_{2009}$ has order $1680$.

-
This is a variant of the answers by Addar Bokobza and by lab bhattacharjee. –  lhf Feb 4 '13 at 12:50