I need to find all the primitive roots of 49. First note, $ ϕ(49) = 42 $

Is there an easier way to go about trying all numbers less than $42$ to find the primitive roots of $49$ if we already know that the primitive roots of $7$ and $49$ are $3$ and $5$?

  • $\begingroup$ You mean "...trying all numbers relatively prime to $49$ to find..." $\endgroup$ – Álvaro Lozano-Robledo Mar 11 '13 at 23:49

If you have found one primitive root $a$, you get all the primitive roots in the form $a^i$ where $\gcd(i,42) = 1$.


Here is another way to see this, so you don't have to take as many powers as in azimut's answer.

Theorem. Suppose that $p$ is an odd prime. If $g\bmod p$ is a primitive root for $\mathbb{Z}/p\mathbb{Z}$ and $g^{p-1}\not\equiv 1 \bmod p^2$, then $g$ is also a primitive root of $p^2$. If $g^{p-1}\equiv 1 \bmod p^2$, then $g+p$ is a primitive root of $p^2$.

Now let's apply this result to your example, when $p=7$. In $\mathbb{Z}/7\mathbb{Z}$ there are $\phi(\phi(p))=\phi(6)=2$ primitive roots, namely $3$ and $5$. In $\mathbb{Z}/49\mathbb{Z}$ there are $\phi(\phi(49))=\phi(42)=\phi(6)\phi(7)=12$. If $h$ is a primitive root modulo $49$, then $h$ is also a primitive root modulo $7$, so $h\equiv 3$ or $5\bmod 7$. There are seven such $h\equiv 3$ and seven such $h\equiv 5\bmod 7$, so we have $14$ candidates for primitive roots, of which $12$ are primitive roots. By the theorem, those which are not primitive roots must satisfy $h^{p-1}\equiv 1 \bmod p^2$. Clearly $$(3^7)^6\equiv 3^{(7\cdot 6)}\equiv 1 \quad \text{ and } \quad (5^7)^6\equiv 5^{(7\cdot 6)}\equiv 1 \bmod 49,$$ by Euler's theorem, because $\phi(49)=42=7\cdot 6$. Since $3^7\equiv 3 \bmod 7$ and $5^7\equiv 5\bmod 7$, by Fermat's little theorem, we conclude that $3^7$ and $5^7$ are the two exceptions: $$3^7\equiv 31 \bmod 49, \quad \text{ and } \quad 5^7\equiv 19 \bmod 49.$$ Hence, the set of primitive roots modulo $49$ are: $$\{3+7k: 0\leq k\leq 6, k\neq 4\} \quad \text{ and } \quad \{5+7j: 0\leq j\leq 6, j\neq 2\}.$$

  • $\begingroup$ +1 Nice alternative solution! My interpretation is that you Hensel-lift the primitive roots mod $7$ to mod $49$, getting all the elements of order $6$. Then you take all candidates for the primitive roots which are not among these Hensel-lifts. $\endgroup$ – azimut Mar 12 '13 at 1:19

Since $\,\phi(49)=42\,$ , for some particular element $\,w\in\Bbb F_{49}^*\,$ one must check whether $\,w^k=1\,$ , for some divisor of $\,42\,$ smaller than $\,42\,$ itself.

For example (all is done modulo $\,49\,$):

$$5^2\neq 1\;,\;\;5^3=27\neq 1\;,\;\;5^6=43=27^2\neq 1\;,\;\;5^7=5\cdot43=5\cdot(-6)=-30\neq1$$

$$5^{14}=(-30)^2=18\neq 1\;,\;\;5^{21}=(-30)^3=-1\Longrightarrow \mathcal ord_{49}(5)=42$$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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