Questions tagged [primitive-roots]

For questions about primitive roots in modular arithmetic, index calculus, and applications in cryptography. For questions about primitive roots of unity, use the (roots-of-unity) tag instead.

36 questions
5k views

Prove if $n$ has a primitive root, then it has exactly $\phi(\phi(n))$ of them

Prove if $n$ has a primitive root, then it has exactly $\phi(\phi(n))$ of them. Let $a$ be the primitive root then I know other primitive roots will be among $\{a,a^2,a^3 \cdots\cdots a^{\phi(n)} \}$ ...
3k views

278 views

Show that $α^k$ is also a primitive element if and only if gcd$(k, q − 1) = 1$.

Let $α$ be a primitive element of $F_q$ . Show that $α^k$ is also a primitive element if and only if gcd$(k, q − 1) = 1$. $1=ak+b(q-1) \implies α^1=α^{(ak+b(q-1))}=α^{(ak)}α^{(q-1)}a=α^ka=α$ i cant ...
893 views

Prove that $a$ is a primitive root $\bmod{p}$ if and only if $-a$ has order $\frac{p-1}{2}$

Consider a prime $p$ $\in\mathbb{N}$ of the form $4t+3$, with $t$ $\in\mathbb{N}$. Prove that a $\in\mathbb{Z}$ is a primitive root $\mod p$ if and only if $-a$ has order $\frac{(p-1)}{2}$. I showed ...
113 views

To show congruence $3^8 \equiv -1 \pmod{17}$

How to show that $3^8 ≡ -1 \pmod{17}$. I have tried by using value of $3^8$ but is there any other method available for solving when more higher powers are included ?
108 views

Solving a congruence using primitive roots

Suppose we know that $3$ is a primitive root of $17$. How can that help us solving $7^x \equiv 6 \pmod {17}$?
1k views

How does one find the primitive roots of a non-prime number? [closed]

Several algorithms exist to find the primitive roots of prime numbers. How does one find the primitive roots of a non-prime number?
primitive roots $g^a \mod{p}$
$p$ prime, $g$ primitive root $\mod{p}$, $0 \leq a \leq p-2$ Show: $g^a \mod{p}$ is a primitive root $\mod{p}$ $\Leftrightarrow$ gcd($a,p-1) = 1$ Ideas: $g^a \mod{p}$ is a primitive root if \$ord(...