Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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!

share|cite|improve this question

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.

share|cite|improve this answer
"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.

share|cite|improve this answer

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.

share|cite|improve this answer

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.

share|cite|improve this answer

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$.

share|cite|improve this answer
This is a variant of the answers by Addar Bokobza and by lab bhattacharjee. – lhf Feb 4 '13 at 12:50

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.