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.

1
vote
1answer
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 ...
0
votes
1answer
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 ...
0
votes
3answers
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
0
votes
1answer
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.
2
votes
1answer
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 ...
0
votes
1answer
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 ...
0
votes
1answer
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)$. ...
0
votes
1answer
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$, ...
2
votes
0answers
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 ...
2
votes
1answer
46 views

Do these two theorems come from Gauß?

$\underline{Theorem \ 1}$ : The group $(\mathbb{Z}/p\mathbb{Z})^{\times}$ is cyclic and its order is $p-1$. $\underline{Theorem \ 2}$ : Let $k\ge 1$ an integer and $p$ an odd prime number. Then $...
0
votes
2answers
43 views

How to show the degree of $\ [ \Bbb Q( \alpha _n +\ \frac{1}{\alpha_n})\ :\ \Bbb Q]$ is $\phi(n)/2$ $\ \alpha_n$ is the primitive n-th root of unity?

I already know that $[ \Bbb Q( \alpha _n )\ :\ \Bbb Q]$ is Euler-phi function $\phi(n)$. But, i have no clue what to do next? Is it possible to find the irreducible polynomial for $\alpha _n +\ \frac{...
0
votes
2answers
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)? \...
2
votes
2answers
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 ...
0
votes
0answers
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 ...
2
votes
2answers
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. ...
0
votes
1answer
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.) ...
0
votes
1answer
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....
1
vote
1answer
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 (...
2
votes
2answers
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 ...
0
votes
1answer
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 ...
0
votes
2answers
90 views

Express complex number in terms of radicals

Let $\zeta=\cos(\frac{2\pi}{16})+i\sin(\frac{2\pi}{16})$ be a 16th root of unity, so that it is a primitive root of unity. I need to explicitly express this number in terms of radicals: $a+ib$, where $...
1
vote
0answers
103 views

Are non-squares primitive roots?

We know that even squares cannot be primitive roots modulo primes.Are all other natural numbers primitive roots mod some p? My heuristic argument goes as follows: the probability that a natural ...
1
vote
1answer
151 views

Prove that it is not a primitive root module $p^2$

I don't even know how to start to prove the following... Let $p$ be an odd prime. Prove that if $a$ is a primitive root modulo $p$ then exactly one of the following integers $a,a+p,a+2p,...,a+(p-1)p$...
0
votes
3answers
248 views

For which Mersenne primes and Fermat primes is 2 a primitive root?

Could you help me answering this question? For which Mersenne primes and Fermat primes is 2 a primitive root? I know that a $a$ is a primitive root modulo $n$ if $a$ generates $\mathbb{Z}_n^*$. A ...
2
votes
0answers
234 views

Primitive elements of finite fields

Let $p$ be a prime number and $q=p^n$ for some positive integer $n$. $F_q[x]$ is the polynomial ring with coefficients in $F_q$. For any $M(x)\in F_q[x]$, define $\mathcal{R}(M(x))\subset F_q[x]$ to ...
1
vote
1answer
25 views

Holomorphic function and deritives

Is it true that there exists a holomorphic function whose derivative is $1/(z^2-1)$? How to tackle problems like these?
1
vote
1answer
48 views

Find $\sum_{i=0}^{k-1}w^{in}$ in terms of $n \in \Bbb N$ being $w \in \Bbb C$ a k-th primitive root of unity.

I need some help with the following problem: Find $\sum_{i=0}^{k-1}w^{in}$ in terms of $n \in \Bbb N$ being $w \in \Bbb C$ a k-th primitive root of unity. I thought of writing it as: $\frac{w^{nk}-...
0
votes
1answer
418 views

How to use Hensel lemma to show that primitive root mod $p$ gives primitive root mod $p^2$ of the form $g + tp$

How to use Hensel lemma to show that primitive root mod $p$, where $p$ is prime, gives primitive root mod $p^2$ of the form $g + tp?$ I tried to start with congruence $g^{p-1} \equiv 1 \pmod p,$ so $...
2
votes
1answer
70 views

Show that if ab has a primitive root with $(a,b) = 1$, then $a<3$ or $b<3$

Show that if $ab$ has a primitive root with $\gcd\left(a,b\right) = 1$, then $a<3$ or $b<3$ I have no idea how to start this question at all... One is that I do not see how 3 is related to ...
0
votes
1answer
701 views

Primitive Roots modulo $p^2$ [duplicate]

Prove that if p is a prime then there exist $\ ϕ(ϕ(p^2 )) = (p − 1)ϕ(p − 1)$ primitive roots modulo $p^2.$ I know how to prove the theorem Let p be prime and let d ∈ N be a divisor of p − 1. Then ...
0
votes
1answer
123 views

Prove that if $g^{(p-1)/2} \equiv -1 (mod \mbox{ } p)$ then its smaller power can't be congruent to 1.

Let $p$ be a prime greater than $2$. Show that $g^{(p-1)/2} \equiv -1 (mod \mbox{ }p)$ implies $g^{k} \not\equiv 1 (mod \mbox{ }p)$ for every $1≤k≤(p-1)/2$.
2
votes
1answer
634 views

Irreducible polynomial, Primitive Polynomial and Minimal Polynomial

I read about irreducible polynomial, primitive polynomial and minimal polynomial and now i am not able to differentiate between them, its chaos in my mind. Can somebody describe what they are actually ...
3
votes
1answer
297 views

If $r$ is a primitive root mod $p$ and $(r+tp)^{p-1} \not \equiv 1 \pmod{p^2}$, then $r+tp$ is a primitive root mod $p^k$

Assume that $r$ is a primitive root of the odd prime $p$ and $(r+tp)^{p-1} \not\equiv 1 (\mod p^2)$. show that $r+tp$ is a primitive root of $p^k$ for each $k \geq 1$. How to check whether something ...
1
vote
1answer
83 views

Help with problem: Let $w$ a 15th-primitive-root of unity. Find all $n \in \Bbb N_{<0}$ such that $\sum_{i=0}^{n-1} w^{5i}=0$

we are starting to see complex numbers in my algebra class. So I have the following problem: Let $w$ a 15th-primitive-root of unity. Find all $n \in \Bbb N_{<0}$ such that $\sum_{i=0}^{n-1} w^{...
1
vote
4answers
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$...
2
votes
2answers
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 ...
1
vote
1answer
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$?
2
votes
3answers
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 ...
2
votes
2answers
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.
1
vote
1answer
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 ...
1
vote
0answers
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 ...
4
votes
1answer
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 ...
2
votes
2answers
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 ...
2
votes
1answer
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 ...
1
vote
2answers
135 views

$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$.
0
votes
1answer
396 views

Proving if $g$ is a primitive root $\pmod n$ and $n$ is prime, then $g^k$ $\pmod n$ is also a primitive root if and only if $\gcd(k, n-1) = 1$

Prove that when $n$ is prime, and $g$ is a primitive root $\pmod n$, $g^k$ $\pmod n$ is always a primitive root whenever $\gcd(k, n-1)$ $=$ $1$. Known Facts: It would be the case that if $\gcd(k, n-...
0
votes
1answer
90 views

Holomorphic function and primitives

I need to prove that $\int_\gamma f'(z)/f(z)dz=0$ for any closed curve. It is given that f is holomorphic and satisfies $|f(z)-1|\lt1$ in the region. And we can assume $f'(z)$ is continuous. I think ...
1
vote
1answer
271 views

Primitive element for each subfield of a cyclotomic extension

Given an odd prime number $p$, a natural number $r$, and a $p^r-th$ primitive root $\zeta=\zeta_p$, I have to find an explicit expression of a primitive element for each subfield of $\mathbb{Q}(\zeta)$...
2
votes
2answers
92 views

Is 2 always a primitive root of 3ˣ?

That is, is it always that $$2^{3^x}\equiv -1\pmod{3^{x+1}}\large?$$
10
votes
4answers
218 views

Any element of $\mathbf{Z}[\xi]$ is congruent to an integer modulo $(1-\xi)^2$ if multiplied by a suitable power of $\xi$

I'm currently reading Kummer's famous paper on Fermat's Last Theorem (if anyone wants the link, I'll post it, but the paper is in German). There's the following statement in there, which should be "...