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

395 questions
48 views

### If n has no primitive roots and a and n are coprime, what can we say about the order of a?

If $n$ has no primitive roots and $a$ and $n$ are coprime, what can we say about the order of $a$? I've Googled this a bit and nothing directly comes up. Ex: if $n = 42$ then we know it has not ...
152 views

### Primitive root of unity in finite local rings

Let $p$ be a prime integer and $R$ be a finite local ring. Assume that $p||R^\times|$. Then by Cauchy's Theorem, there always exists a primitive $p$ root of unity in $R^\times$. Here $R^\times$ is a ...
86 views

### How many solutions does $x^{50} \equiv 1 \mod 181$ have?

How many solutions does $x^{50} \equiv 1 \mod 181$ have? I know that $\varphi(181)$ is $180$ so $x^{180} \equiv 1$ for all $x$ as $181$ is a prime. I'm not sure how to go forth from here
105 views

### Calculate the order of 3 modulo 257

How on earth would you go about this? I would start with g is a primitive root then g^i congruent to 3 but then I get stuck thereafter.
244 views

### $\mathbb{Z}_p^*$ has a primitive $p - 1$-th root of unity (p-adic)

I am trying to prove that $\mathbb{Z}_p^*$ has a primitive $p - 1$-th root of unity. I already proved that $\mathbb{Z}_p^*$ has a $p - 1$-th root of unity using Hensel's lemma. Here is my proof: if ...
533 views

### Show that 3 is a primitive root mod 257

So we know the order of 3 must be 256 yet this is too big number to calculate by hand (or calculator) so we use the fact that there exists another primitive root, g, such that 3 is congruent to g^i ...
208 views

### proof of primitive roots algorithm

We know the following from elementary number theory: (1) for $gcd(a,n) =1, a^{\phi(n)} \equiv 1 (mod \, n)$ (2) $ord_na \mid \phi(n)$ (3) $a$ is a primitive root $mod \, n$ iff $ord_na = \phi(n)$. ...
113 views

### Prove that if the $\mathrm{ord}(p)a =3$, then $\mathrm{ord}(p)(a+1) = 6$, $p$ prime [duplicate]

I couldn't answer this question. This only one. It looks simple, but I got stuck. Here is the image of the question. The number $12$. Sorry for my english. Prove that if the $\mathrm{ord}(p)a=3$, ...
235 views

### Subgroups and corresponding fixed fields of Galois group of primitive 24th root of unity.

I have been asked to determine the lattice of subgroups of $G=\Gamma(\mathbb{Q}(\zeta):\mathbb{Q})$ where $\zeta$ is a primitive $24^{th}$ root of unity. I am then asked to determine their ...
46 views

159 views

### How to prove $r^{\phi(m)/2} \equiv -1$ (mod $m$) if $r^{\phi(m)} \equiv 1$ (mod $m$)?

If we have a primitive root $r$ for $m > 2$ (whatever composite or prime), that $r^{\phi(m)} \equiv 1$ (mod $m$), how can we show that \begin{align} r^{\phi(m)/2} \equiv -1\text{ }(\text{mod } m)? \...
47 views

### How to interpret this comment from OEIS A050229?

I've been wracking my brain trying to gleam some insight into this comment from 2007: Numbers n for which there is a permutation of 0..n-1 such that each number is the sum of all the previous, plus ...
157 views

### Verify that $x$ is a primitive root modulo $n$

I have a question. How can we the quickest to test whether $x$ is a primitive root modulo $n$? On the Wikipedia page I found information about a possible algorithm. This algorithm, however, must ...
598 views

### Why are primitive roots called generators?

I learned recently that the reason that g is commonly used to denote a primitive root is because it stands for "generator". I also know that this has something to do with the non-zero residues. ...
106 views

### Hint for Number Theory question.

I need a hint for this question please: Find the sum of the orders mod 83 over all elements of the set $\{1,2,3,\ldots,82\}$. (If multiple elements have the same order, add that term multiple times.) ...
100 views

### Simple question about generating random primitive roots for a large prime

I am sure this question has been answered before but I could not find any similar question. In Diffie-Hellman protocol implementations we can try to find a large primes using safe prime formula (i.e....
105 views

### Question About Primitive Root of Unity

I stumbled upon one of these exercises in my textbook and thought it would be a great review for my exam. Here is the question: Let $n$ be an odd positive integer, and let $\zeta$ be a primitive (...
846 views

### Determine every degree 4 primitive polynomial in $GF(2)[x]$

Determine, showing all reasoning, every degree 4 primitive polynomial in $GF(2)[x]$. I think $x^4+x+1$ might be one but I do not know how to show it, could anyone explain? Also after this, how would ...
187 views

### Find primitive-$n$-th roots of unity over finite field $\mathbb{F}_a$??

Is there efficient methods to find primitive-$n$-th roots of unities over $\mathbb{F}_a$?? In other word, find $\zeta$ such that, $\zeta^n \equiv 1$ where $\zeta \in \mathbb{F}_a$ Also, is there ...
90 views

418 views

460 views

### $m>2$ and $n > 2$ are relatively prime $\Rightarrow$ no primitive root of $mn$

Show that if $m>2$ and $n > 2$ are relatively prime, there is no primitive root of $mn$ I know that $mn > 4$, and thus $\varphi(mn)$ is an even number so that I might write $\varphi(mn) = 2x$...
1k views

### Prove that $r$ is a primitive root modulo $p$ if and only if $r^{(p−1)/q}\not\equiv 1\pmod{p}$

Suppose $p$ is an odd prime. Prove that $r$, with $\gcd(r, p) = 1$, is a primitive root modulo $p$ if and only if $r^{(p−1)/q}\not\equiv 1\pmod{p}$ for all prime divisors $q$ of $p − 1$. The only ...
45 views

### Is $g$ mod $p$ a generator for the multiplicative group mod $p^2$?

How would one go about proving/disproving whether $g$, a multiplicative generator mod $p$, is also a multiplicative generator mod $p^2$?
164 views

### Let $p$ be an odd prime. Suppose that $a$ is an odd integer and also $a$ is a primitive root mod $p$. Show that $a$ is also a primitive root mod $2p$.

Let $p$ be an odd prime. Suppose that $a$ is an odd integer and also $a$ is a primitive root modulo $p$. Show that a is also a primitive root modulo $2p$. Any hints will be appreciated. Thanks very ...
59 views

### Prove that if $r$ is a primitive root modulo $m$, and $(a, m) = (b, m) = 1$, then $r^a \equiv r^b \pmod{m}$ implies $a\equiv b \pmod{\varphi(m)}$

Prove that if $r$ is a primitive root modulo $m$, and $(a, m) = (b, m) = 1$, then $r^a \equiv r^b \pmod{m}$ implies $a \equiv b \pmod{φ(m)}$. Any hints will be appreciated. Thanks so much.
113 views

### Is primitive root or order in number theory relate with order of element in cyclic group?

I just read abstract algebra and found notation of cyclic group (I don't read the whole yet ) the order in number theory state $a^{b}\equiv 1(mod N)$ and Cyclic group state $a^{n}=e$ or I not sure ...
98 views

### Finding primitive root mod n?

in wikipedia, https://en.wikipedia.org/wiki/Primitive_root_modulo_n#Finding_primitive_roots, it says there is no formula to compute primitive root mod n. and in the footnote 8, it seems that there ...
2k views

### Every primitive root modulo an odd prime is a quadratic nonresidue

This is my proof of the title statement. Is it correct? Suppose $a$ is a primitive root and quadratic residue modulo $p$. Then by definition $$\operatorname{ord}_p(a)=p-1$$ But Euler's ...
340 views

### $a$ is a primitive root modulo a prime $p$; $ab\equiv1\bmod p$; prove $b$ is a primitive root modulo $p$

Let $p$ be prime. Prove that if $a$ is a primitive root modulo $p$ and $ab\equiv1\bmod p$, then $b$ is a primitive root modulo $p$. I understand the definition of primitive roots. I am having trouble ...
331 views

### Assuming that $r$ is a primitive root of the odd prime $p$ prove that $r^{(p-1)/2}\equiv -1 \pmod p$ holds

I know if $r$ is primitive root $r^{^{n}}\equiv a\pmod n$ from the set of residue $\{1,2,3....(n-1)\}$ but if change to $r^{(p-1)/2}\equiv -1 \pmod p$. My assumption: It's no longer be primitive ...
### $h^{\frac{p-1}{2}} \equiv 1 \bmod p$ and $g^x \equiv h \bmod p$ for a primitive root $g$ $\iff$ $x$ is even
Let $g$ be a primitive root for the odd prime $p.$ Suppose $g^x \equiv h \pmod p$. Show that $x$ is even if $h^{\frac{p-1}{2}} \equiv 1\pmod p$ and $x$ is odd if $h^{\frac{p-1}{2}}\equiv -1\pmod p$.