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

392 questions
475 views

### Proof of Fermat's Little Theorem using Primitive Roots

I just learned about primitive roots today, and then I thought of this proof of Fermat's Little Theorem. Seeing that most proofs of this theorem aren't simple, I think I'm either completely wrong in ...
79 views

### Multiplicative order: an exercise

I've got this problem: Determine an integer with (exactly) multiplicative order $22$ mod $1331$ Is there a general way to procede in any case with this kind of exercises? Thank you!
79 views

### If $g$ is a primitive root, show that $a$ is a $d$th power $\iff$ $a\equiv g^{kd}$

I wanted to ask you to help me with this exercise in numer theory. Here it is: If $g$ is a primitive root modulo $p$ and $d|p-1$, show that $g^{(p-1)/d}$ has order $d$. Show also that $a$ is a $d$...
455 views

### Primitive roots modulo n

How do I find a primitive root for a given $n$? For which $n$ does a primitive root exist (I would have guessed it's for all $n$ which are not divisible by 8)? Is there a systematic way, to constuct ...
87 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 ...
48 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.
141 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 ...
3k views

403 views

### Counting Primtive 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 ...
342 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. ...
### 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}$.