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

488 questions
Filter by
Sorted by
Tagged with
90 views

### suppose a>1 is an integer, and p is an odd prime number.

Suppose $a>1$ is an integer, and $p$ is an odd prime number. Prove that each odd prime factor of $(a^p)-1$ which does not divide $a-1$ should be in the form $2pt+1$. My Approaching: ($a^p)-1$ is ...
49 views

### Prove or Disprove the following statemnet

Prove or Disprove the following statement: For each integer n>1 and each divisor d of φ(n), there is an integer a of order d modulo n. Any help would be appreciated.
201 views

### if $b^k$ is a primitive root, then $b$ is a primitive root

Any hints or strategies would be greatly appreciated: If $m$ is an integer and $b^k$ is a primitive root mod $m$, then $b$ is a primitive root mod $m$. I am reviewing material from my elementary ...
4k views

466 views

### Counting Primitive Roots modulo a prime with Totient Function

Let $\psi: \mathbb{N}^+ \rightarrow \mathbb{N}^+$ be the Totient function which counts the number of positive integers coprime to its argument. Let $p$ be a prime number. Then the number of ...
376 views

### primitive roots of primes exercise ( is related to Sophie German theorem)

Let p and q be primes with $q\gt p$ such that p is not a factor of q-1. As q is a prime, we know that for any integer x we can write $x^{q-1}$ in the form $x^{q-1} = kq+1$ for some integer k. ...
7k 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)} \}$ ...
### Prove sum of primitive roots congruent to $\mu(p-1) \pmod{p}$
Suppose that $p$ is a prime. Prove that the sum of the primitive roots modulo $p$ is congruent to $\mu(p − 1) \pmod{p}$.