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.

Filter by
Sorted by
Tagged with
1 vote
0 answers
28 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
70 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
28 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 ...
user avatar
1 vote
1 answer
30 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 $\...
  • 163
1 vote
0 answers
48 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 ...
  • 163
0 votes
0 answers
50 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
58 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'...
  • 987
1 vote
2 answers
43 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 $(...
2 votes
1 answer
31 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.3k
0 votes
1 answer
231 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$ ...
1 vote
1 answer
85 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 ...
4 votes
0 answers
142 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
27 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
17 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
133 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: ...
  • 301
1 vote
1 answer
33 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 $\...
  • 517
0 votes
2 answers
39 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 ...
0 votes
1 answer
191 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 ...
0 votes
0 answers
46 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
33 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
35 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^\...
0 votes
1 answer
59 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
79 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 $...
0 votes
0 answers
21 views

Lower bound on the number of monic irreducible polynomials of prime degree $p$

I know that this boils down to the lower bound on the equation for $n\geq 1$, $$\frac1n\sum_{d\mid n}\mu(n/d)p^d$$ where $\mu$ is the möbius function and that $\mu(1)=1$ so $p^d$ is a term.
0 votes
0 answers
23 views

Primitive roots proof

I know how to use lifting the exponent lemma but one thing I didn't understand in both the proofs is the sufficient condition e.g why is it enough to prove those two? The first one is showing $3^n$ ...
0 votes
0 answers
56 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.5k
0 votes
1 answer
100 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
55 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 ...
0 votes
1 answer
63 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 ...
0 votes
1 answer
73 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 ...
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,...$ (...
  • 395
1 vote
0 answers
78 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^...
5 votes
1 answer
49 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.4k
0 votes
0 answers
66 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
180 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 ...
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,626
3 votes
1 answer
125 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
127 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
93 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,752
3 votes
1 answer
229 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,444
2 votes
1 answer
147 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
285 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)$, ...
1 vote
0 answers
80 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 ...
-2 votes
1 answer
740 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
159 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$, ...
user avatar
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
140 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
2 3 4 5
12