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