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!
 A: 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.
A: 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.
A: 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.
A: 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.
A: 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$.
