Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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.

0
votes
0answers
30 views

In general, do primes of the form $a×2^{n}+1$always have primitive $2^n $th roots of unity (modulo that prime)?

EDIT: Title had an extra +1 in the 2's exponent For context, in competitive programming, problems which require a number theoretic transform usually ask for the answer modulo $998244353=7\times17\...
1
vote
5answers
72 views

For which primes p will there be a solution to x^3 + 1 ≡ (mod p) other than x ≡ - 1 (mod p)

I'm trying to learn more about modular arithmetic by practicing some problems, but I'm having some difficulty with this one. For which primes p will there be a solution to x^3 + 1 ≡ (mod p) other ...
0
votes
2answers
31 views

Given that $5$ is a primitive root of $73$, find all solutions to $x^3 - 1 ≡ 0$ (mod $73$).

I'm working through some problems with primitive roots and needed some help on this problem, specifically how do we use the fact that $5$ is a primitive root to solve this? Given: $5$ is a primitive ...
1
vote
0answers
25 views

Primitive roots in arithmetic progression

Let $a$ be a primitive root modulo odd prime. Show that in an arithmetic progression $a+kp$, where $k = 0,1,\dots,p-1$ there is exactly one number that is NOT a primitive root modulo $p^2$. It is ...
1
vote
1answer
40 views

Prove that number is a primitive root for all $k$ in range

Let $a$ be a primitive root for $p > 2$ where $p$ is prime. Show that $a^p+kp$ for $k = 1,\dots,p-1$ are $p-1$ distinct primitive roots modulo $p^2$. What I have done: First of all it is easy to ...
1
vote
0answers
34 views

What is the best upper bound for “how often” a number n is a primitive root modulo a prime p?

Let $n$ be a non-square positive number. The Artin Conjecture states that there are infinitely primes $p$ for which $n$ is a primitive root. Question: Given a number $n$, what is the best upper bound ...
0
votes
1answer
20 views

Why are the Galois groups that correspond to extensions which adjoin primitive roots of unity given by the group of units mod n

Considering all the following in the context of Galois theory. I believe, given say the primitive $9^{th}$ root of unity, that this will have as its minimum polynomial , the cyclotomic polynomial $\...
0
votes
1answer
36 views

How does Fermat's Little Theorem help find primitive roots of unity?

I am asked to find the primitive roots of unity mod 23, and recommended to use Fermat's Little Theorem to help simplify calculation. I know that, once I've found one, I can find all others by finding ...
6
votes
1answer
143 views

Prove that there are infinitely many primes which are primitive roots modulo $N$

Assuming $N$ has a primitive root, show that there are infinitely many primes which are primitive roots modulo $N$. It is obviously true using Dirichlet's theorem on primes, but I want to prove ...
-2
votes
2answers
93 views

Given 2 is a primitive root mod 19, find all solutions to x^12 ≡ 7 (mod 19) (a) x^12 ≡ 6 (mod 19)

I'm stuck on (another) problem under Number Theory. There are quite a few gaps on what was covered in my class so I'm having quite a bit of trouble. Could you please help me solve the following ...
0
votes
0answers
27 views

Any finite field of $q$ elements has exactly $\Phi(q-1)$ primitive roots

Is the following prove of the above statement correct? $\bullet\ $Any finite field of $q$ elements is isomorphic to $\mathbb{F}_q$ and we know that $\mathbb{F}_q^*$ is a cyclic group of $q-1$ ...
1
vote
1answer
25 views

Use primitive root to prove if $a^{\phi(m)/2}\equiv 1\pmod m$ then $a$ is a quadratic residue modulo $m$.

This is trivial in arguments of quadratic residues, but I couldn't solve it using primitive root. The problem seeks to use primitive root to be proved. Problem: Let $m>2$ be an integer having a ...
0
votes
1answer
13 views

If $(a,m)=(b,m)=1$ and if $(\exp_m(a),\exp_m(b))=1$, prove that $\exp_m(ab)=\exp_m(a)\exp_m(b).$

If $(a,m)=(b,m)=1$ and if $(\exp_m(a),\exp_m(b))=1$, prove that $$\exp_m(ab)=\exp_m(a)\exp_m(b).$$ The notation $\exp_m(a)$ is denote the smallest positive integer $n$ such that $a^n\equiv 1\pmod m$. ...
1
vote
0answers
38 views

Certain conditions for primitive roots of $n$.

Let $a$ be a primitive root for modulo $n$. Then, $a^{\frac{\phi(n)}{2}}\equiv-1\pmod{n}$. I have a question for its converse. In general, its converse is false. Is it possible to make(it means '...
1
vote
1answer
48 views

Number of solutions of $x^e \equiv c \mod p$

We have to find the number of solutions to the equation:- $$x^e \equiv c \mod p$$ where $c \not\equiv 0\mod p$. For $c=1$, we can prove that the above has $\gcd(e,p-1)=d$ solutions in the following ...
1
vote
0answers
61 views

Is this a valid proof of Euler's product formula for the totient function?

I will attempt the proof using induction. But first, a lemma: Lemma 1: If $ n = p^{\alpha} $, where $ p $ is prime and $ \alpha\in\mathbb{N} $, then $ \phi(n) = n(1-\frac{1}{p}) $. $ \underline{...
1
vote
0answers
36 views

show this a primitive root question [closed]

if $n$ be positive integers,and such (1):$$\prod_{1\le i\le n,(i,n)=1}i\equiv -1\pmod n$$ (2):there exsit $a,$ such $a$ is a primitive root modulo $n$. show that $(1)\Longleftrightarrow (2)$ ...
2
votes
2answers
53 views

Prove that a primitive $q$-th root of unity is in the algebraic closure of $\Bbb F_p$

Let $p$ and $q$ be odd primes. Let $\Omega$ be the algebraic closure of $\Bbb F_p$. Let $\omega$ be a primitive $q$-th root of unity. Show that $\omega \in \Omega$. How do I show that? Please help me ...
0
votes
2answers
31 views

A proof of theorem about primitive roots [closed]

I have a such equation: $$ {x}^{n}-1=0 $$ I have n complex roots. For example:$${x}^{7}-1=0$$ $${x}_{1}=1; {x}_{2} = {(-1)}^{\frac{1}{7}}; {x}_{3}=-{(-1)}^{\frac{2}{7}}; ...;{x}_{7}={(-1)}^{\frac{6}{7}...
0
votes
1answer
48 views

$\zeta_n^k$ is primitive if and only if $(k,n) = 1$ [duplicate]

Show that for $k \in \mathbb{Z}$: Is $\zeta_n$ a primitive $n$-th root of unity, then $\zeta_n^k$ is primitive if and only if $(k,n) = 1$. I only need the backwards direction: $\zeta_n^k$ is ...
0
votes
0answers
43 views

Transforming sum of phases to geometric series of sine function

While trying to understand Shor's algorithm, I encountered this formula: $p(y) = \frac{1}{2^nm}\big|\sum^{m-1}_{k=0}e^{2\pi ikry/2^n}\big|^2$. Now for $y=j2^n/r+\epsilon$, according to my textbook, ...
0
votes
1answer
37 views

$(e^{2\pi i}){}^n \neq e^{2\pi i n}$ where $n\in\mathbb{N}$?

When I type these equations into a calculator I get $({e^{2\pi i}}){}^n = 1$ and something else for $e^{2\pi i n}$. Is that due to the imprecision of the calculator or does the inequality follow ...
0
votes
0answers
36 views

Primes $p$ in which $3$ is a primitive root modulo $p$ [duplicate]

I want to show that if $3$ is a primitive root modulo $p$ if $p$ is a prime of the form $2^n+1$ for some $n>1$. First, I wrote $3^{p-1} \equiv 1 \mod p$. Then writing it as $(1+2)^{p-1}$, we see ...
2
votes
1answer
43 views

Which primes divide $x^2-5$?

Which primes divide $x^2-5$? What I have tried: If $p$ divides $x^2 -5 $ then: $$x^2= 5\pmod{p}$$ Therefore, from Euler's extended theorem we get that for primes s.t $\gcd(5,p)=1$ (which are all ...
0
votes
0answers
53 views

Determine a Normal Basis for Galois Extension of $\mathbb{Q}$ with primitive pth root of unit (p prime)

Let p be a prime, $\xi_p \in \mathbb{C}$ a primitive p-th unit root and $K = \mathbb{Q}(\xi_p)$. Give a normal basis for $K/\mathbb{Q}$. I know, that a basis of $L/K$ (finite and galois) is ...
3
votes
0answers
43 views

solutions of gold APN functions using trace function

The Gold APN is defined as $F(x)=x^{2^{k}+1}$ in $GF(2^n)$, where $\gcd(k,n)=1$. The differential uniformity computed using $F(x)=F(x+a)=b$ as following: $x^{2^{k}+1} + (x+a)^{2^{k}+1}=b$ $x^{2^{k}+...
0
votes
0answers
39 views

Given 2 is primitive root (mod p), showing that every non-zero element of Z(p) is expressable as power of [2] (mod p)

I'm trying to find out how I would go about showing this: Given a prime number p >= 2, suppose 2 is a primitive root modulo p. Show that every non-zero element of Z(p) can be written as a power of [2]...
0
votes
0answers
59 views

Relation between residues and primitive roots modulo $p$

I got a very satisfiying answer to my question on the relation between primeness and co-primeness of numbers which can be defined in a somehow symmetric way: $n$ is prime iff $$(\forall xy)\ ...
4
votes
1answer
67 views

Prove that $\eta - \omega \notin \mathbb{Q}$ where $\omega$ and $\eta$ are two differents n-th primitive roots $\in \mathbb{C}$

Let $n \in \mathbb{N}$ be a natural number, and be $\omega$ and $\eta$ two differents n-th primitive roots in $\mathbb{C}$. Prove that $\eta - \omega \notin \mathbb{Q}$ My attempt was to follow the ...
2
votes
1answer
62 views

PRIMES in P paper - Lemma 4.7 - why are the polynomials $X^m$ distinct in $F$?

I'm working through the original AKS paper, available here: https://www.cse.iitk.ac.in/users/manindra/algebra/primality_v6.pdf. There's a single transition which I don't know how to justify, I will ...
0
votes
2answers
31 views

Let the extention $GF(p^m) \supset GF(p)$ that contains roots of $p(x)=x^{p^{m}}-1$. Show that those roots are distinct and that forms a field

I want to rewrite a question not so well written on this site and clarified by Mr. Lahtonen (thank you again). So here the question: Let the extention $GF(p^m) \supset GF(p)$ that contains roots ...
4
votes
1answer
169 views

A question about a primitive root mod $p=2^{2^k}+1$, where $p$ is prime.

Let $p=2^{2^k}+1$ be a prime where $k\ge1$. Prove that the set of quadratic non-residues mod $p$ is the same as the set of primitive roots mod $p$. Use this to show that $7$ is a primitive root mod $p$...
0
votes
1answer
118 views

The set of the primitive roots modulo $p$, with $p$ a fermat prime

"Let $p$ be a prime of the form $2^{2^{n}}+1$, with $n \in \mathbb{N} $ (This means $p$ is a Fermat prime) Using Euler's Criterion, prove that the set of primitive roots mod $p$ is equal to the set ...
1
vote
1answer
124 views

Show that $−g$ is also a primitive root of $p$ if $p\equiv 1 \pmod{4}$, but that $ord_p(−g) = \frac{p−1}{2}$ if $p \equiv 3 \pmod{4}$. [duplicate]

Let $p$ be an odd prime and let $g$ be a primitive root $\pmod{p}$. Show that $−g$ is also a primitive root of $p$ if $p \equiv 1 \pmod{4}$, but that $ord_p(−g) = \frac{p−1}{2}$ if $p \equiv 3 \pmod{...
1
vote
2answers
114 views

When g and -g are both primitive roots

The question states: Let $g$ by a primitive root of the odd prime $p$. Show that $-g$ is a primitive root , or not, according as $p \equiv 1 \pmod 4$ or not. For me, I cannot see any connection ...
0
votes
1answer
63 views

Show that if $p|(a^{2^n}+1)$, then $p = 2$ or $p\equiv 1 \pmod{2^{n+1}}$

As the title indicates, I do not know how to proceed. There is a hint to prove it. The hint says that: show that if $p>2$ then a is of order $2^{n+1} \pmod p$. But I do not see any connection ...
2
votes
2answers
75 views

If $a$ is of order $3$ mod a prime $p$, then …

The question says: Prove that if $a$ is of order $3$ modulo a prime $p$, then $1+a+a^2\equiv 0 \pmod p$. Moreover, $a+1$ is of order $6$. For the First Part: The typical idea is to start with $a^...
3
votes
1answer
46 views

Is there any primitive root of $p$ which is not primitive root of $p^2$ without $1$? [closed]

Is there any primitive root of $p$ which is not primitive root of $p^2$ without $1$ (since $1$ is a primitive root of $2$ but $1$ is not a primitive root of $4$)? Are there other examples?
3
votes
0answers
43 views

Some questions concerning the generators of cyclic groups

Let $g(p)$ be the least positive primitive root of the prime $p$, the primitive roots being the generators of the cyclic group $\mathbb{Z}_{p-1}$. These are the values for the first prime numbers: $$...
1
vote
1answer
158 views

How to find all primitive roots modulo 121?

This question is different from this question as I want to find all primitive roots, and not just some. Is my following approach correct? We have $121=11^2$, with $11$ an odd prime, and $2 \ge 1$, ...
0
votes
1answer
26 views

Solutions of $x^2 \equiv \pm 2 \ (\text{mod} \ p)$ and primitive root modulo $p.$

If $p = 8n+1$ is a prime and $r$ is a primitive root modulo $p,$ then the solutions of $x^2 \equiv \pm 2 \ (\text{mod} \ p)$ are given by $x \equiv \pm(r^{7n} \pm r^n) \ (\text{mod} \ p).$ Again, ...
1
vote
0answers
37 views

n is primitive root for odd prime p. If -n is primitive root iff p = 4k+1 for some integer k

if $n$ is primitive root for odd prime $p$, then $-n$ is also a primitive root for $p$ $\iff p = 1 \text{ mod } 4$ I am having trouble solving this question, can someone show to me how to solve it? ...
0
votes
1answer
18 views

$\zeta$ is a p-th primitive untary root iff $-\zeta$ if a 2p-th primitive unitary root, with $p$ an odd prime

$\Rightarrow$ $(-\zeta)^{2p}=(-\zeta^p)^{2}=1$ and if $i \in[{1,2p-1}]$ there is $k \in[0,p-1]$ such that $i=2k+1$ if is odd and $2k$ if is even so $(-\zeta)^{i}=(-\zeta)^{2k}=(\zeta^k)^{2}\neq 1$ ...
0
votes
1answer
35 views

How to Simplify $\mathbb{Q}(\zeta_4,\zeta_8 , \zeta_{12},\zeta_6 )$

If $mdc(m,n)=1$ then $\mathbb{Q}(\zeta_m,\zeta_n )=\mathbb{Q}(\zeta_{mn} )$,but what if the degree of the roots are divisors and multiples of each other? I guess that $\mathbb{Q}(\zeta_4,\zeta_6, \...
0
votes
0answers
24 views

Subfields of Galois Extensions and association with Galois Groups

Let $\mathbb{K}\subseteq \mathbb{L}$ be a Galois extension with order $n$. If $p$ is a prime divisor of $n$, show that exists a subfield $\mathbb{M}$ of $\mathbb{L}$ such that $[\mathbb{L},\mathbb{M}]...
0
votes
1answer
31 views

Finding primitive roots modulo $x$

I'm just starting with number theory and by now I know how to test whether a given number $\alpha$ is a primitive root mod $p$ or not. But I'm not sure yet how it works if $\alpha$ isn't given. I saw ...
1
vote
1answer
36 views

Proof of $(\mathbb{Z}/p^k \mathbb{Z})^\times\cong\mathbb{Z}/\phi(p^k) \mathbb{Z}$

While learning some material about primitive roots, I read some algebraic approach of the proof of the existence of primitive roots. I read this wikipedia article, however, I got a little bit ...
1
vote
0answers
128 views

Primitive nth roots of unity related to the complex nth roots of 1.

I just cannot seem to wrap my head around this problem and would really appreciate some guidance. So I know that a primitive $n^{th}$ root of unity is a complex number $z$ such that $z^n = 1$ but $z^m ...
1
vote
1answer
88 views

How to prove that $g$ or $g+p$ is a primitive root modulo $p^a$ for a primitive root $g$ modulo $p$?

I wish to prove the following: If $p$ is an odd prime and $g$ is a primitive root modulo $p$, then either $g$ or $g+p$ is a primitive root modulo every power of $p$. The only reference I can find ...
0
votes
2answers
32 views

Why is this function equal to zero?

Say that I have a primitive root of unity $\omega$. Given $p \neq 0$, and $1-\omega^p \neq 0$, the following function is supposed to equate to zero, but I could not understand it. \begin{equation} \...