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
2answers
61 views

How to show the $p$ minus primitive root is also a primitive root for $p \equiv1 \pmod {4}$

Let $p$ be a prime such that $p \equiv1 \pmod {4},$ and let $r$ be a primitive root mod $p$. I wonder how to show that $p-r$ is a primitive root mod $p.$
1
vote
0answers
44 views

Question related to N-th cyclotomic polynomial, principal N-th root of unity and residue class of X

I am struggling to understand a couple of statements in a cryptography-related paper. I think I lack some maths background. Can you help me understand it ? Here are the statements: We consider the ...
5
votes
1answer
439 views

Efficient algorithms for Primitive roots where time-complexity is $\leq O(\sqrt{n})$

I have an algorithm for primitive roots for input number $n$ that I believe is $O(n)$ currently. I also have separate algorithms for $\varphi(n)$ and $factorise(n)$ which I believe are both $O(\sqrt{n}...
0
votes
1answer
26 views

must a primitive root be invertible?

I think so, consider $g$, a primitive root. We know that $g^{\phi(m)} \equiv 1 \pmod {m}$. Then, $g^{-1} = g^{\phi(m) - 1}$ since: $$ gg^{-1} = g\cdot g^{\phi (m) - 1} = g^{\phi(m)} = 1$$ As an ...
2
votes
1answer
90 views

Prove $\sum\limits_{j=1}^{p-1} j\left(\frac{j}{p}\right) = 0 $ for an odd prime $p$ with $p\equiv 1\text{ mod } 4$

I want to show for an odd prime $p$ with $p\equiv 1\text{ mod } 4$, that $$\sum\limits_{j=1}^{p-1} j\left(\frac{j}{p}\right) = 0 $$ where $\left(\frac{j}{p}\right) $ is the Jacobi symbol. I got ...
1
vote
1answer
38 views

Showing two different definitions of a primitive root are the same

In a book im reading the following definition is given for a primitive root: "An integer $a$ is called a primitive root mod $p$ if $\overline{ a }$ generates the group $U(\mathbb{Z}/p\mathbb{Z})$. ...
0
votes
1answer
46 views

On multiplicative and additive properties of cyclotomic polynomials

Is there explicit relation between $\Phi_{a+b}(x)$, $\Phi_{ab}(x)$, $\Phi_{a}(x)$ and $\Phi_{b}(x)$ at general coprime or non-coprime $a,b\in\Bbb Z$? If $a,b$ are distinct primes then we have $x^{ab}-...
2
votes
1answer
88 views

Smallest prime $p$ which every integer $< n$ is a primitive root $\mod p$

Another interesting question related to primitive roots is what is the smallest prime $p$ for which the primes less than $n$ are primitive roots $\mod p$. The sequence of primes would be $[p, p_2, p_3,...
0
votes
1answer
59 views

Exercise 34 from Needham Visual Complex Analysis 1. Cyclotomic polynomial for the pth (p prime )root of unity

The exercise is: Show that $\Phi_p(z) =1+z+z^2+z^3+...+z^{p-1}$ I started: If $p$ is prime, all the $p$th roots of unity are primitive (apart from 1) so can be expressed as $w, w^2, w^3,$ etc where $...
4
votes
0answers
200 views

Primitive element and choice of irreducible polynomial

It is known that every finite field of the same order $p^k$ are isomorphic. So, $F_p[x]/\langle q(x)\rangle$ leads to the same field for any choice of irriducible k-degree $q(x)$ over $F_p[x]$. But, ...
1
vote
0answers
175 views

Get primitive root of 1024 bit prime number in sage

How to find the primitive root of a 1024 bit prime number in sage? primitive_root(p) takes forever to calculate.
0
votes
2answers
59 views

Primitive roots in integer rings of number fields with class number 1

In number fields that are PIDs, i.e., with class number 1, we have unique factorization of integral elements into primes, much like we do in $\Bbb Z$. Suppose $\pi$ is such a prime element in $R$, the ...
0
votes
1answer
36 views

Index arithmetic for $9x^8 \equiv b \pmod{17}$

I wish to find all b such that $9x^8 \equiv b \pmod{17}$ has a solution using index arithmetic. I have figured out that 3 is a primitive root, giving: $$\text{ind}_39+8\text{ind}_3x \equiv 2+8\text{...
1
vote
1answer
110 views

Solving a congruence using primitive roots

Suppose we know that $3$ is a primitive root of $17$. How can that help us solving $7^x \equiv 6 \pmod {17}$?
0
votes
1answer
144 views

$2$ cannot be a primitive root of a prime $F_n$

$2$ cannot be a primitive root of a prime $F_n = 2^{2^n} + 1$ where $n\ge 2$ I've understood that the fact that $F_n \equiv 1 \pmod{8}$ for $n\ge 2$ might be helpful here, but I don't see how (Though ...
1
vote
1answer
41 views

Why is it the case that if $a$ is a primitive root of $x^p=1$, then $\frac{x^p-1}{x-1}=(x-a^2)(x-a^4)…(x-a^{2(p-1)})=1+x+x^2+…+x^{p-1}$?

If $p$ is an odd prime. Why is it the case that if $a$ is a primitive root of $x^p=1$, then $\frac{x^p-1}{x-1}=(x-a^2)(x-a^4)...(x-a^{2(p-1)})=1+x+x^2+...+x^{p-1}$? I can see why $\frac{x^p-1}{x-1}=1+...
0
votes
1answer
69 views

Showing that $f(x)=x^2+2x+3$ is irreducible and primitive.

So I am given the following polynomial $f(x)=x^2+2x+3\in \mathbb{Z}_5[x]$ and asked to show that it is first irreducible and then that it is primitive. So in terms of irreducibility, this is ...
0
votes
1answer
101 views

What will be the behavior of the roots?

I have following equation $$(1-x)-(1-x)\frac{a}{(1-p)}x^{-\frac{k}{2}}=g$$ where $k>2$, $0<p<1$ $a>0$ and $g>0$. I want to know how will the roots behave with $p$. In essence will the ...
6
votes
1answer
532 views

Find a primitive root of $71$.

In my Number Theory Class we found that $7$ was a primitive root of 41 by first finding two integers who have order $5$ and $8$ $modulo 41$ respectively, these being $16$ and $3$. Since $16(3)=7(...
2
votes
2answers
72 views

Determine all solutions of the congruence $y^2≡5x^3\pmod7$ in integers $x$, $y$.

Determine all solutions of the congruence $y^2≡5x^3\pmod7$ in integers $x$, $y$. I learned about primitive roots and the theory of indices. By trial, I check that $3$ is a primitive root of $7$ and $...
1
vote
1answer
57 views

Eigenvalues are roots of cyclotomic polynomial

I am reading Lyndon and Shupp's 'combinatorial group theory'. At page 25 it is stated that if $g$ is an element of finite order $n$ in $\mathbb{GL}(2, \mathbb{Z})$, its eigenvalues must be roots ...
1
vote
1answer
529 views

Product of coprimes less than n

I observed that if $n$ has a primitive root then $c_1 \cdot c_2 ... \cdot c_{\phi(n)} \equiv -1 \ mod \ n$ otherwise, $c_1 \cdot c_2 ... \cdot c_{\phi(n)} \equiv 1 \ mod \ n$ where $c_i$'s are ...
0
votes
1answer
122 views

Find all primitive elements $e = aw+b$ in the field GF$(25)$ where $w^2 = 2$.

In the finite field GF$(25)$, each element is of the form $e = aw+b$ where $w^2 = 2$ in GF$(5)$ and $a$ and $b$ are ${0, 1, 2, 3}$ or ${4}$, elements in GF$(5)$. For each element $e ,\exists m$ such ...
2
votes
1answer
138 views

Probability of Primitive Root (Mod 43)

Probability of Primitive Root (mod 43) Q: If you independently select 5 random integers from the reduced residue system (mod 43), What is the probability that at least one of your integers is a ...
1
vote
1answer
91 views

Need some help with a proof about primitive roots.

I'm having trouble understanding this theorem: If $g$ is a primitive root of $m$, then the remainders modulo $m$ of $g,g^2,...,g^{\varphi (m)}$ are the $\varphi (m)$ natural numbers that are ...
0
votes
1answer
50 views

Modulo arithmetic and sum of arbitrary powers of a primitive root of unity.

Prove that if $w$ is a primitive nth root of unity, then $1 + w^k + (w^k)^2 + (w^k)^3 + \cdots + (w^k)^{n-1} =0$ iff $k \neq 0$ mod $n$. Sorry for the terrible formatting. Also, I don't know ...
0
votes
2answers
56 views

Finding the splitting field of $\Phi_{21}(x)$ over $\mathbb Q$

In another question I asked how I would find the miminal polynomial of a primitive nth root of unity over $\mathbb Q$, which was very well answered and easy to follow. Taking the same example, let $...
1
vote
2answers
198 views

Product of quadratic residues in terms of primitive root

Let $a$ be a primitive root for prime $p(\geq 3)$. Show that the product of all non-zero quadratic residues is congruent to $a^\frac{p^2−1}{4}$ and that the product of quadratic nonresidues is ...
2
votes
0answers
104 views

Theorems on Primitive Roots

Let g be a primitive root modulo $p$($p$ is an odd prime) with $g^{p-1}\ncong{1}\ (mod\ p^{2})$. I am interested in proving that $$g^{(p-1)p^{m-2}}\ncong{1}\ (mod\ p^{m})$$ for every $m\geq{2}$ So ...
1
vote
1answer
145 views

primitive roots of primes

Suppse $g$ is a primitive root modulo $p$ (a prime) and suppose $m\mid{p-1} ,\ (1<m<p-1)$How many integral solutions are there of the congruence $$x^m-g\equiv{0}\ (mod\quad p)$$ So far it seems ...
2
votes
2answers
208 views

Number of $k$th Roots modulo a prime?

So I'm having a bit of trouble proving the following theorem: Suppose that $p$ is a prime, $k \in \mathbb{N}$ and $b \in \mathbb{Z}$. Show that the number of $k$th roots of $b$ modulo $p$ is either $...
2
votes
1answer
67 views

Evaluate $\prod_{k=1}^{n-1} \cos \frac{k \pi}{n}$ where $\text{gcd}(n,k)=1$ and $n$ is odd

Prove that $\prod\limits_{1 \le k \le n-1,\gcd(n,k)=1} \cos \frac{k \pi}{n}=\frac{(-1)^{\varphi(n)}}{2^{\varphi (n)}}$ where $n$ is an odd number. I used the same method as here but how can we ...
2
votes
1answer
267 views

How to find a primitive root modulo $5^{10}$?

I know how to find primitive roots of relatively small primes. But how can one possibly find a primitive root modulo $5^{10}$? I can't test every single number less than $5^{10}$. Is there a fast way ...
3
votes
1answer
98 views

Does Artin's conjecture imply that the reciprocal sum of primes with a given primitive root would diverge?

Artin conjectured that every non-square integer $a\ne -1$ is a primitive root for infinitely many primes. Here it is on Wikipedia: Artin's conjecture on primitive roots. The conjecture also includes a ...
0
votes
1answer
38 views

Given $g^x$ and $g^y$, identify $g^{xy}$ from $g^r$ in an ideal scenario

It is know that given a large prime $p$ and a primitive root of $\mathbb{Z}_p^*$, $g$, and two numbers $g^x$ and $g^y$ (modulo $p$), it's impossible to distinguish $g^{xy}$ from $g^r$ where $x$, $y$ ...
0
votes
1answer
160 views

Fast fourier transform

In fast fourier transform, what are the square and the square root of $\omega_{128}$, the primitive 128th root of 1? Is it possible for you to help me on this one?
1
vote
0answers
894 views

confusion on how to find primitive roots (find primitive root mod 23, 46, 529, 12167)

We were asked to find primitive root mod $23$, $46$, $529$, $12167$. My lecturer gave us a hint in finding primitive root mod $23$, but I am confused about his reasoning. My lecturer said $a$ would ...
2
votes
0answers
67 views

How to prove that all the eigenvalues of this matrix have modulus $\sqrt{n}$?

Let $\zeta$ be a primitive $n$-th root of unity. Prove that all eigenvalues of the matrix $\left(\begin{matrix} 1 & 1 & 1 & \cdots & 1\\ 1 & \zeta & \zeta^2 & \cdots & ...
2
votes
2answers
76 views

a (simple?) property of primitive roots

Let $p\neq 2$ be a prime and let $a$ be a primitive root modulo $p^k$ satisfying $p^k|a^{p^k-1}-1$ and $p^k\nmid a^{\dfrac{p^k-1}{q}}-1$ for all prime divisors $q$ of $p^k-1$. Then $k=1$. I was ...
1
vote
1answer
55 views

Galois theory question

Let α be a complex primitive 43rd root of 1. Prove that there is an extension field F of the rational numbers such that $[F(\alpha): F] = 14$. I don't know how to start, can someone help me out?
5
votes
2answers
155 views

simplify a numerical expression without calculator

The following term: $$\sqrt{2017^2-2018^2+2019^2}$$ is the same as this term: $$\sqrt{2018^2+2}$$ how can one show without the need of a calculator that these are the same? The original question was ...
0
votes
1answer
38 views

Complexity of finding a root in ring P

$G$ and $P$ are known prime. $$b = a^G \bmod P$$ What is the complexity time of finding $a$ from $b$?
4
votes
2answers
54 views

Prove that $\gamma^{\frac{q-1}{2}}=-1$ in $\mathbb{F}_q$ when $q$ is an odd prime power and $\mathbb{F}_q^*=<\gamma >$.

I have written a proof for this, however I think there may be a simpler way to go about it and am curious for any suggestions. Also I don't fully see where my proof would fail if $q$ was even (other ...
1
vote
1answer
66 views

$f(X)=X^{16}-X \in \mathbb F_2 [X]$ ,order of primitive roots, polynomial of minimal degree

Given is the polynomial $f(X)=X^{16}-X \in \mathbb F_2 [X]$. It factorizes into $f(X)=X(X+1)q(X)$, where $q(X)=X^{14}+X^{13}+\dots +X+1$. Now, let $\alpha$ be a primitive root of $\mathbb F_{16}$ ...
1
vote
1answer
70 views

Checking understanding of Order, Primitive Roots

I dont seem to understand how primitive roots work. I've outlined what I think, if anyone can tell me what I'm misunderstanding I'd really appreciate it! To calculate the order of 5 modulo 18, our ...
0
votes
0answers
31 views

$p_1^a - p_2^b g \equiv 0 \pmod{p_3}$ for some primitive root $g$, prime $p_3$, and fixed prime powers $p_1^a,p_2^b$

I was wondering whether one can prove for some fixed integer powers of fixed primes $p_1^a$ and $p_2^b$ that there exists some prime $p_3$ which has a primitive root g, such that: $p_1^a - p_2^b g \...
2
votes
4answers
103 views

Primitive elements of $\mathbb{F}_5[X]/[X^2-2]$

I am trying to find a primitive elements of $\mathbb{F}_5[X]/(X^2-2)$, so I was thinking about checking all the powers of an element in this field and see if they yield all the non-zero elements in ...
0
votes
1answer
45 views

A proposition about primitive roots.

Proposition. Let $p$ be a prime number congruent to 1 mod 6. Suppose $g_1$ and $g_2$ are primitive roots mod p such that $g_1 \ne g_2$. By $H_1$ we denote the subgroup of $ \mathbb F_{p} ^ {\times} \...
2
votes
1answer
124 views

If g is a primitive root modulo $N$, then g is a primitive root modulo $D$, where $D|N$.

Let g be a primitive root modulo $N\ge2$ and $D\ge 2$ a divisor of $N$. Show that the reduction modulo D of g is a primitive root modulo D. I've tried using Gauss' Theorem, but I'm not quite sure how ...
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 ...