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.
607 questions
1 vote
0 answers
90 views
Maximum number of pairwise primitive root primes
What is the largest number of distict prime numbers that are primitive roots of one another pairwise? The answer is either finite or infinite. For the latter, we may consider the follow-up question: ...
- 4,952
1 vote
0 answers
139 views
Property of primes with primitive root $2$
Let $a(n)$ be A001122, i.e., an integer sequence of primes with primitive root $2$. I conjecture that iff $n$ is prime that belong to $\{a(n)\}$, then for $1 \leqslant k \leqslant n-1$ there always ...
user929945
1 vote
2 answers
109 views
Primitive root of unity can be decomposed in primitive roots.
Given a $n$-th primitive root of unity, i.e. a number $e^{2\pi i k/n}$ such that $gcd(k, n)=1$, I want to show that if I take $n=lm$ with $l$ and $m$ coprime than I can express $e^{2\pi i k/n}$ as the ...
- 4,488
9 votes
1 answer
441 views
Existence of a Linear Recurrence Modulo $p$ with Period $p^2 - 1$
Let $p$ be a prime number. Prove there is an integer $c$ and an integer sequence $0 \leq a_1, a_2, a_3, \dots < p$ with period $p^2 - 1$ satisfying the recurrence $$ a_{n+2} \equiv a_{n+1} - c \...
- 103
3 votes
1 answer
209 views
Theorem 3.9 from Janusz - Algebraic Number Fields (Edition 2)
Unramified Extensions The unramified extensions of a completion of a number field at a nonarchimedean prime are easily described and have a number of very special properties. We give just a few ...
- 813
1 vote
2 answers
118 views
Compute all subextensions of $\mathbb{Q}(\xi)$
Let $\xi \in \mathbb{C}$ be a primitive seventh root of unity. Determine all the subextensions of $\mathbb{Q}(\xi)$ I´ve found the subextensions but I need help finishing the argument. This is my ...
- 1,004
8 votes
1 answer
385 views
Product Identity modulo $p=8k+5$
Let $p$ be a prime of the form $p = 8k + 5$, and let $g$ be a primitive root modulo $p$. Prove that: $$ (g^4 + 1)(g^8 + 1)(g^{12} + 1)\cdots(g^{4k} + 1) \equiv g^{k(k+1)} \pmod{p}. $$ Here's what I ...
- 139
0 votes
0 answers
31 views
$g$ a primitive root modulo $p^2$ for $p$ an odd prime $\Rightarrow$ $g$ a primitive root modulo $p^k$ for every $k \in \mathbb{Z}^+$ [duplicate]
I've been trying to prove this result to no avail. Previously I managed to prove that if $p$ is an odd prime and $g$ a primitive root modulo $p$, then $g$ or $g + p$ is a primitive root modulo $p^2$. ...
- 972
0 votes
0 answers
53 views
Prove that $(1^2+1)(2^2+1)...((p-1)^2+1)\equiv 4 \pmod p$ when $p\equiv 3 \pmod 4$ [duplicate]
This is a problem from my teacher in his primitive roots lecture. First we have $x^2 +1 \equiv (p-x)^2 + 1\pmod p$, then $$(1^2+1)(2^2+1)\cdots((p-1)^2+1) \equiv [(1^2+1)(2^2+1)\cdots((\frac{p-1}{2})^...
- 139
0 votes
0 answers
73 views
Understanding a proof that if $p$ is an odd prime, $g$ is primitive root mod $p$, then $\exists x$ s.t. $g + px$ is primitive root mod $p^k,k\geq 1$
I am trying to understand a part of the following claim, which seems a bit weaker than many other results related to primitive roots that I have seen but which I still would like to understand ...
- 1,673
1 vote
1 answer
104 views
Trying to understand how the statement "$2$ is a primitive root for $3^k,k\geq 1$" is proved with the use of the lifting lemma
If you want to jump straight into the end of the preamble or the start of the proof steps I have written, go to End of preamble/start of proof. There are a few posts on this site addressing the ...
- 1,673
0 votes
1 answer
188 views
Efficient method for finding primitive polynomials in $GF(p^n)$?
Is there an efficient method for finding primitive polynomials, especially for larger fields like $GF(2^{64})$ or larger? For $GF(2^n)$, XOR and carryless multiply can be used for polynomial math ...
- 872
0 votes
2 answers
70 views
Primitive roots modulo $n$ and $2n$, but $a$ is even.
I'm trying to prove the following, after seeing a similar post about $a$ being an odd primitive root (Primitive roots modulo $n$ and $2n$.): if $n \in \mathbb{N}$ is odd and $a \in \mathbb{Z}$ is an ...
- 93
1 vote
0 answers
36 views
If $a, b$ are a primitive root modulo a prime $p$, then $ab$ is not a primitive root modulo $p$ [duplicate]
Given an odd prime number $p$, prove that if $a,b \in \mathbb{Z}$ are primitive roots modulo $n$, then $ab$ is not a primitive root modulo $n$. Someone suggested this question: Product of two ...
- 93
4 votes
2 answers
111 views
Primitive polynomial for non-prime $\mathbb{F}_q$
I need to computationally find (at least one) primitive element $\theta$ of $\mathbb{F}_{q^n}$, where $q=p^k$ is a prime power for some prime $p$. The goal is to express all the elements of $\mathbb{F}...
- 68