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.
559
questions
0
votes
0
answers
27
views
Diagonal patterns in a plot related to Artin's Conjecture about primitive roots
This image displays the following information. The pixel in the ($a$-th row, $k$-th column) is
\begin{equation}
\begin{cases}
\text{gray} & \text{if } a \geq p_k \\
\text{white} & \text{if } a ...
- 17
1
vote
0
answers
29
views
$(a+pk)^{p-1}≡1+ph−pka^{p−2} \mod{p^2}$, for some $h∈\mathbb{Z}$; if $k≢ah \mod{p}$, then $a+pk$ is a primitive root mod $p^2$.
Started an introductory number theory class and totally stuck on some homework after hours of effort. Feel like I'm so close but can't do the final bit to solve it and starting to wonder if my ...
- 11
1
vote
1
answer
79
views
Show that $2$ is not a primitive root of $8k + 7$
I'm attempting to show that $2$ is not a primitive root of primes of the form $p = 8k + 7$. I know that, to do so, I must show that $2$ has order less than $\phi(p)$ modulo $p$ (where $\phi$ denotes ...
- 1,281
2
votes
0
answers
33
views
Finding primitive roots including negative sign
I commonly run into the following question such that if $p$ and $q=4p+1$ are both odd primes prove that $2$ is primitve root modulo q . However , i could not prove it for other number that are given ...
user1121946
2
votes
1
answer
35
views
How to prove that $\sum_\limits{k=1\\(k,p-1)=1}^{p-1}g^k \equiv \mu(p-1)$ (mod p) for prime p and primitive root g
p is a prime and g is a primitive root modules p, and I want ot prove that:
$\sum_\limits{k=1\\(k,p-1)=1}^{p-1}g^k \equiv \mu(p-1)$ (mod p)
$\mu(x)$ is the Möbius function
I know how to deal with $\...
- 369
1
vote
0
answers
57
views
Prove that the roots of cyclotomic polynomial $\Phi_{p-1}(x) \equiv 0 (mod~p)$ are exactly the primitive roots mod p
$p$ is a prime, and $\Phi_{p-1}(x)$ denote the cyclotomic polynomial of order $p-1$. And I want to show the following:
$g$ is a solution of the congruence $\Phi_{p-1}(x) \equiv 0 (mod~p)$ if and only ...
- 369
0
votes
0
answers
51
views
Show that the polynomial $x^4+x+1$ is primitive over $\mathbb{F}_2$ [duplicate]
I've been struggling for hours and so far have shown the polynomial is irreducible, $p(0) \neq 0$, and monic.
All there is left to prove is that the polynomial is of order $15$.
Then I can use a ...
2
votes
1
answer
63
views
Calculation of generalized Artin's constants
Let $T(p)$ be the period of the decimal expansion of $1/p$, for prime $p$ (e.g. $1/7=0.\overline{142857}\rightarrow T(7)=6$). It is known that
$$T(p)=\frac{p-1}{t}$$
for some integer $t$. Then, Artin'...
- 979
1
vote
2
answers
48
views
Characterizing generators for the multiplicative group of a finite field.
Fix a finite field $\mathbb{F}_p$ and consider its multiplicative group $\mathbb{F}_p^\times$, which we know is cyclic. Is there an general way to characterize this group's generators (the primitive $(...
- 678
2
votes
1
answer
37
views
Explicite upper bound for the smallest primitive root?
In this Wikipedia article some upper bounds for the smallest primitive root $g$ modulo a prime $p$ are given, but the first is implicite (what is the constant $C$ depending on $\epsilon$) and the ...
- 80.6k
0
votes
1
answer
369
views
Order, primitive roots modulo 19 [closed]
b. Suppose $a$ is some primitive root of $19$ (it must exist for any prime!).
What is the order of $a^2$, $a^3$, $a^4$, and $a^5($mod $19)$?
What elements $a^k($mod $19)$, where $k =2, \ldots 18$ ...
- 3
1
vote
1
answer
108
views
A primitive root modulo p is a primitive root modulo $p^2$ if and only if $g^{p-1} \not\equiv 1 \mod{p^2}$
$p$ is an odd prime. I'm starting with number theory and I'm completly stuck with this question. In general, I don't really know how to approach the proves. Then I'm also supposed to prove that either ...
- 85
4
votes
0
answers
145
views
Given an odd prime $p$, is there another odd prime $q$ such that $p$ is a primitive root modulo all powers of $q$?
As the title says, I want to know if for every odd prime $p$, there is another odd prime $q$ such that $p$ is a primitive root modulo $q^m$ for all $m\ge1$. For small $p$ such as $p=3,5,7$, I could ...
- 199
0
votes
0
answers
28
views
Integral of functions that have oscillating discontinuous points(not finite) aren't differentiable?
I know that integral of removable discontinuous functions are differentiable but jump discontinuous aren't. However, When 2xsin(1/x)-cos(1/x) is integrand, which is derivative of x^2sin(1/x) has no ...
0
votes
0
answers
23
views
Let a and g be primitive roots modulo p (where p is an odd prime). Prove that ag is not a primitive root modulo p. [duplicate]
Let a and g be primitive roots modulo p (where p is an odd prime). Prove that ag is not a primitive root modulo p.
I stumbled upon this problem and was confused about how to solve it, could anyone ...
4
votes
0
answers
134
views
How to solve the equation in algebraic number theory?
First step: When $p\equiv 1 \pmod{ 3}$, prove that there exists a pair $(a,b)$ of integers such that $4p=a^2+27b^2$, $a\equiv 1 \pmod{ 3}$ and a is unique (the proof of the first step).
Second step: ...
- 299
1
vote
1
answer
36
views
Understanding a proof relating to Kummer extensions
Theorem: Let $\zeta_m$ be a primitive mth root of unity, and $K$ a field. If $\zeta_m \in K$, then every $\mathbb{Z}/m\mathbb{Z}$-extension of $K$ is of the form $K(\alpha^\frac{1}{m})$ for some $\...
- 527
0
votes
2
answers
50
views
Counting primitive elements in a finite field extension
I want to find the no. of elements $\alpha \in \mathbb{F}_{3^5}$ so that $\mathbb{F}_{3}(\alpha) = \mathbb{F}_{3^5}$(minimal polynomial of $\alpha$ is of degree 5). I know such things do exist but how ...
- 3,381
0
votes
1
answer
214
views
Vanishing sums of integral linear combinations of roots of unity
Let $\{ \xi^{i} \}_{i=1}^{n}$ be $n$-th roots of unity for some positive integer $n$. It is well known that if $n$ is a prime integer, there will be $n-1$ primitive $n$-th roots of unity which are ...
- 3
0
votes
0
answers
48
views
Order of an integer $a$ relation with the Legendre symbol $(a/p) = -1 \pmod p$
I am self studying number theory from David M. Burton's book Elementary Number Theory.
Example $9.7$ explains about $3$ as a primitive root of primes $F_n = 2^{2^n}+1$ these are of the form $p= 12k+5$...
- 160
1
vote
1
answer
34
views
Do we have an upper bound for Artin’s conjecture on primitive roots?
Let $a$ be an appropriate integer and $\pi_a (x)$ denote the number of prime $p$ such that $a$ is a primitive root modulo $p$. Do we have an upper bound of $\pi_a(x)$ such as $\pi_a(x) \ll x/\log x$? ...
- 101
2
votes
1
answer
39
views
About The Order of an Integer
In this bolg It says
$x=ord_{n}b$ and $ord_n = $ the least positive integer x such that $b^x\equiv $ 1 (mod n)
and below it says $b^x\equiv $ 1 (mod n) if and only if $ord_{n}b$ | x and then it ...
0
votes
1
answer
38
views
Showing polynomial $p(x) = x^2 −3 \in\mathbb{F}_7[x]$ is prime in $E[x]$ and $x^3 - 2\in\mathbb{F}_7[x]$ factors into linear terms in $E$
Here we define the set of equivalence classes $E[x] = \mathbb{F}_7[x]/(x^3 - 2)\mathbb{F}_7[x]$. I'm not sure if showing $p(x)$ is prime is equivalent to showing that it is a primitive root of $E^\...
- 55
0
votes
1
answer
60
views
Proof about least nonnegative residue modulo m when m has no primitive roots
What is the least nonnegative residue modulo 𝑚 of the product of all positive integers not exceeding 𝑚 and relatively prime to 𝑚, if no primitive root modulo 𝑚 exists? Prove your assertion.
I know ...
- 1
1
vote
0
answers
80
views
Number of roots in cyclotomic polynomial $\Phi_{15}[x]$ in $\mathbb F_p$
I'm trying to understand why if the $gcd(p-1, 15) = d \neq 15$, then there are zero roots (since if it's $=15$, there are exactly 8). I was thinking that since a solution to $x^d - 1$ is relevant if $...
- 55
0
votes
0
answers
58
views
Find the sum of the $m$-th powers of the primitive roots mod p for a given prime p and a positive integer $ m$.
Wikipedia has the result that Gauss proved that for a prime number p the sum of its primitive roots is congruent to $\mu(p−1)\pmod p$ in Article 81.
also see:Prove sum of primitive roots congruent to $...
- 91.6k
0
votes
1
answer
112
views
Find sum of primitive roots of $z^{36} − 1 = 0$ [closed]
I am trying to understand this concept of sum of primitive roots of unity and here is a typical problem based on it.
$z^{36} − 1 = 0$
- 11
-4
votes
2
answers
56
views
How to calculate the integral of $x\frac{\text{d}f}{\text{d}x}$? [closed]
How can we calculate this integral $ \int x \frac{\text{d} f}{\text{d} x} \,\text{d}x $ ?
I have tried both integration per partes and change of variables, but it doesn't seem to work. Of course, we ...
- 3
0
votes
1
answer
64
views
Are primes of the form $6k+1$ a cube modulo $n$, if $3\nmid n$ and none of the prime factors of $n$ is of the form $6k+ 1$?
I wonder if we can assume the following statement to be true in general:
Let $p$ be a prime of the form $6k+1$ and $n<p$ a natural number less than $p$. If $3$ does not divide $n$ and none of the ...
- 1,554
0
votes
1
answer
76
views
How to solve the congruence $x^{30} ≡ 81x^6 \pmod{269}$ using primitive roots(without indices)?
So I know that 3 is a primitive root of 269.
How can I solve $x^{30} ≡ 81x^6 \pmod{269}$
Even if I substitute $x$ with $3^y$, where $y$ lies between 0 and 267, I can’t get any solutions.
- 91
1
vote
0
answers
43
views
I've followed two different methods to find congruence with primitive roots but have two different answers
So I'm using the fact that 2 is a primitive root modulo 53, I'm solving $x^5 \equiv 8\mod{53}$
Originally I was trying to rewrite both sides in terms of two so had the following:
let $x=2^y$ for y ...
- 11
4
votes
0
answers
59
views
Probability of a prime $p=3\pmod 4$ occurring in A213052
As you may notice, A213052 contains primes mostly congruent to $1\pmod 4$ (in fact, all of the known ones are except $3$).
Consider the sequence of smallest primes $p_n$ such that $2,3,5,7,11,13,...$ (...
- 405
1
vote
0
answers
84
views
How can you use a primitive root to solve a modular congruence?
I've read through this answer to get some ideas: Solving a congruence using a primitive root
But my problem is slightly different and it's thrown me off in terms of understanding the logic.
I have $ x^...
- 79
5
votes
1
answer
55
views
Maximal order with primitive determinant in $\operatorname{GL}_n(\mathbb{F}_q)$
The following question has come up in a facet of a current project. Having an answer (hopefully affirmative) will help me design and test some computational simulations.
$\mathbb{F}_q$ denotes the ...
- 17.5k
0
votes
0
answers
87
views
[Proof]if p and q are odd prime, and q=2p+1,then -4 is primitive root of q
how to proof if p and q are odd prime, and q=2p+1, then -4 is primitive root of q.
I think quadratic residue of q is useful, but I cant use it effectively.
if for example. p=3, then q=7, and the ...
- 13
0
votes
0
answers
55
views
proving no primitive roots exist modulo $2^n$ for n $\geq$ 3
Ive been asked to prove by induction that no primitive roots exist modulo $2^n$ for n $\geq$ 3.
I have proven true for base case $n=3$, and assumed to be true for $n$.
I'm now stuck at this point:
$${...
2
votes
0
answers
198
views
A primitive root modulo $p^k$ is primitive modulo $p^{k+1}$,for $k\geq 2$.
I am a graduate student of Mathematics.I am stuck with the following number theory problem:
Let $p$ be an odd prime.Prove that any primitive root modulo $p^k$ is a primitive root modulo $p^{k+1}$, for ...
- 2,957
3
votes
0
answers
67
views
A sum of root of $-1$ modulo n
Find the sum of positive integers $n$ less than $2021$ such that $n^{3 \cdot 7 \cdot 23} \equiv -1 \pmod{2021}$.
I was making an elementary number theory problem using the year number $2021=43 \cdot ...
- 1,646
3
votes
1
answer
130
views
Finding primitive roots modulo n code
I'm trying to translate some code into another language but struggling to understand the math behind it.
The code is from this answer and is as follows:
...
- 137
1
vote
1
answer
137
views
Understanding Neukirch´s proof
I´m studying algebraic number theory from Neukirch´s book. I´m reading the Proposition 10.2 which says:
A $\mathbb{Z}$-basis of the ring $O$ of integers of $\mathbb{Q}(\zeta)$ is given by $1, \zeta, \...
- 121
4
votes
0
answers
94
views
Intuition behind this strange heuristic for primitive roots modulo $p$?
Let $p$ be an odd prime. Define $S(p)$ as the sum of all primitive roots modulo $p$ taken from $\left[-\frac{p-1}2,\frac{p-1}2\right]$.
Now here's the strange thing. If the primitive roots were '...
- 7,827
3
votes
1
answer
231
views
Given a prime $p$ and a positive integer $a \not \equiv 0,1 \pmod p$, show that S = $\sum^{p-1}_{i=1} a^i \equiv 0 \pmod p$
The origin of this question is actually a different question:
Show that all primes except 2 and 5 divide infinitely many elements of $B :=\{1,11,111,1111,\cdots\}$.
It's relatively straightforward ...
- 2,535
2
votes
1
answer
159
views
If $r$ is a primitive root of $p$ and $p^2$, then show that it is also a primitive root of $p^3$
If $r$ is a primitive root of $p$ and $p^2$, then show that it is also
a primitive root of $p^3$
This is part of a bigger proof and I'm stuck at understanding this part.
Here some lines of proof from ...
- 599
0
votes
0
answers
329
views
sagemath GF(p^n) calculations
Is there a way to generate the primitive elements in $GF(p^n)$, in say Sagemath, and perform operations with these elements?
For example, using the irreducible polynomial $p(x)=1+x+x^3$ in $GF(2^3)$, ...
- 27
1
vote
0
answers
86
views
For what primes is $6$ a primitive root?
While thinking about an unrelated problem, I had to decide whether $6$ was a primitive root with respect to multiple prime moduli. I could discover no obvious pattern as to primes for which $6$ is a ...
- 6,766
-2
votes
1
answer
870
views
How to find primitive root modulo of 23? [duplicate]
These types of questions are repeated here zillionth time, but I am yet to find an useful process(hit and trial or any other process) to find primitive root modulo. Can you help me. I need this for ...
- 21
1
vote
1
answer
166
views
Proof Verification: a primitive root modulo $p^n$ is also a primitive root modulo $p$
I'd like some advice on my approach for this exercise, which has been giving me some hesitancy. Let $\alpha$ be a primitive root modulo $p^n$. Show that $\alpha$ is also a primitive root modulo $p$, ...
user711703
0
votes
0
answers
104
views
Why it is sufficient to look at prime divisor of $p-1$ when finding generators of $\mathbb{Z}_p^*$?
Let's say that I want to find the generators of $\mathbb{Z}_p^*$, where $p$ is a prime number. I found the following necessary and sufficient condition:
An element $x \in \mathbb{Z}_p^*$ is a ...
- 269
0
votes
1
answer
143
views
Show that there is no modulus with an odd prime number of primitive roots
Show that there is no modulus with an odd prime number of primitive roots. I'm not really sure how to approach this at all. I was thinking of using the property that there exists a primitive root ...
- 3
1
vote
0
answers
58
views
Solving the equivalent congruence I found and using it to derive the solution to the original congruence (elementary number theory)
I am trying to solve following problem. I have done the entire problem, so I'm not asking anyone to do the problem for me. But I need some confirmation on whether or not the very last part of my ...
