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
0 votes
0 answers
44 views

about sum of unity roots

$\zeta_p $ is a primitive $p$-th root of unity in $\mathbb C$.for any $d \in N$, define that $G_d=\Sigma_x(\zeta_p)$^$x^d$, for all $x \in F_p$. Show that the degree over $Q$ of $G_d$ is equal to ...
z2014430's user avatar
2 votes
0 answers
55 views

Artin's conjecture on primitive roots for perfect powers

Let $a\neq -1,0,1$ be an integer. Write $a=(b^2c)^k$, where $b^2c$ is not a perfect power, and $c$ is squarefree. Artin's conjecture on primitive roots states that the asymptotic density of the set of ...
Jianing Song's user avatar
  • 1,779
4 votes
1 answer
111 views

A question about a proof of Proth's Theorem

This theorem is The number $N=2^n\cdot k+1$ with $k<2^n$ is prime if and only if there exists $a$ with $a^{(N-1)/2}\equiv -1\mod N$ This proof is $\Longrightarrow$ : If $N$ is prime, let $a$ be ...
hbghlyj's user avatar
  • 2,464
3 votes
1 answer
53 views

Two primitive roots add to a third

Primitive roots are useful in analyzing the multiplicative structure of the numbers mod $p$, for $p$ a prime. I wondered if there was anything that could link the multiplicative and additive structure ...
ViHdzP's user avatar
  • 4,622
0 votes
1 answer
42 views

Proof of identity on sum of powers of primitive root.

Let $q = p^e$ for some prime $p$. Consider the trace function $\mathrm{Tr}_{\mathbb{F}_q/\mathbb{F}_p}:\mathbb{F}_q\to \mathbb{F}_p$ defined by $\mathrm{Tr}_{\mathbb{F}_q/\mathbb{F}_p}(x) = \sum_{i=0}^...
PTrivedi's user avatar
  • 1,001
2 votes
3 answers
130 views

Application of "Every nonzero residue modulo a prime can be represented as a power of a primitive root."

I am reading a machine learning paper, and this paragraph below doesn't quite make sense. How is x+y (mod p−1) and x*y (mod p) equivalent? Suppose p = 5 and x = 3 and y = 4, then clearly 7 mod 4 =3 ...
Snowball's user avatar
  • 1,099
2 votes
1 answer
120 views

Number of zeros in the decimal representation of the powers of 5

I am trying to solve this problem: Prove that for every natural number $m$, there exists a natural number $n$ such that in the decimal representation of the number $5^n$ there are at least $m$ zeros. ...
Email's user avatar
  • 61
0 votes
0 answers
56 views

The existence of a primitive root

Prove that there exists a primitive root $g$ modulo $p$ ($p$ an odd prime) such that $g^{p-1}\not\equiv 1 \pmod {p^2}$ So far, I have been able to prove that if $g$ is a primitive root modulo $p$ ($p$...
Alex Nguyen's user avatar
  • 1,229
1 vote
0 answers
39 views

Vinogradov's proof that $U_{p^{\alpha}}$ is cyclic. How to prove $p^{r-1} (p-1) \mid \delta$ for $1 \leq r \leq \alpha$

The proof of Vinogradov that $U_{p^{\alpha}}$ ($\alpha \geq 1$) is cyclic for an odd prime $p$, has a part that I don't understand. We take $g$ a primitive root of $U_p$. And, at a certain point of ...
niobium's user avatar
  • 1,187
1 vote
4 answers
226 views

How to find a primitive element for $\mathbb F_{11}$

This is a pretty dumb question considering this is the very first question in my exercises (on a section about finite fields). First, the the group of units $\mathbb F_{11}^*$ is $\mathbb{Z}/10\mathbb{...
iwjueph94rgytbhr's user avatar
2 votes
0 answers
52 views

When does this Galois theorem "variation" holds?

Im reading about solvability by radicals in different books, more concretely in Fields and Galois Theory by Patrick Morandi and Introduction to abstract algebra by Benjamin Fine, etc. In the second ...
eldebarva's user avatar
0 votes
1 answer
63 views

Primitive root mod $p^2$ and $p^4$

If $a$ is not a primitive root mod $p^2$ for a prime $p$. What is the fastest way of checking if $a$ is (or it is not) a primitive root mod $p^4$? Is there any useful trick? Thanks!
Vemba's user avatar
  • 75
0 votes
1 answer
47 views

Number theory: Where did I go wrong with solving this polynomial congruence? [duplicate]

Question: Find an integer that solves the congruence $$x^{83}\equiv 7 \pmod{139}$$ My working: Let $b$ denote some primitive root of the prime mod 139, and let $$x\equiv b^y\mod 139$$ for some ...
Holland Davis's user avatar
0 votes
1 answer
111 views

Check if a polynomial is primitive over a galois field using Magma calculator

I want to check if the polynomial $f(x) = 1 + x^{18} + x^{29} + x^{42} + x^{57} + x^{67} + x^{80}$ is primitive over the Galois Field $GF(2^{80})$ using the Magma Calculator (http://magma.maths.usyd....
Divye Kalra's user avatar
0 votes
0 answers
33 views

Question about a proof of $\phi(r)$ incongruent integers

Hello I have a particular question, about the proof of the following theorem: Theorem: If $r|p-1$, with $p$ an odd prime, there are $\phi(r)$ incongruent integers which have order $r$ modulo $p$. ...
TreeBook1's user avatar
0 votes
0 answers
60 views

How do I prove that the primitive element of a field extension are this way.

I'm doing an introductory course of field theory and there is one excercise that as easy as it seems it bring me on my nerves. It states: Let $α_1, \dots, α_n ∈ \mathbb{C}$ be the roots of an ...
Floralys's user avatar
2 votes
0 answers
104 views

Is it possible to create factors of $p_n\#$ which cannot create any primitive root of $p_{n+1}$?

(Edited for clarity.) Take the primorial of the $n$th prime $p_n$ by using $H=\prod_{i=1}^np_i$. Does there exist an $n$ such that there exists $d\mid H$ where there are no factors of $d^{p_{n+1}-1}$ ...
abiessu's user avatar
  • 8,125
0 votes
1 answer
65 views

Let p be a prime number with p≡3 (mod 4) and let r be a primitive root modulo p . Prove that $\mathrm{ord}_p(-r) = (p-1)/2.$

I only could write this: Let p = 4k + 3 where k is an nonnegative integer. Since r is a primitive root modulo p . $r^{(p-1)/2} ≡ - 1 $ mod p. So $r^{2k+1}≡ -1$ mod p $(-r)^{2k+1}=-1*(r)^{2k+1}$ $-1*(...
Damla's user avatar
  • 3
0 votes
0 answers
36 views

Is zero a discrete logarithm?

In the book Discrete Mathematics and Its Application, it said "Suppose that p is prime and r is a primitive root modulo p. If a is an integer between 1 and p-1, that is, a nonzero element of $\...
FallInClouds's user avatar
0 votes
1 answer
77 views

I've some problem in the definition of primitive root in the Discrete Mathematics and Its Applications [duplicate]

In the book, he said that "A primitive root modulo a prime p is an integer r in $\mathbb Z_p$ such that every nonzero element of $\mathbb Z_p$ is a power of r." It is very different to other ...
FallInClouds's user avatar
0 votes
0 answers
24 views

How can I find all primitive roots of 41? [duplicate]

I know how to do it with smaller numbers by testing,but here we have φ(φ(41))=16 solutions out of 40 possibilities.I think I somehow have to use indices. Actually how do I even find 1 primitive root?...
Alex Brown's user avatar
2 votes
0 answers
82 views

Cyclotomic Polynomials and The Existence of Infinite Prime Power

Prove that there exist infinitely many positive integers n such that all prime divisors of $n^2 + n + 1$ are not greater than $\sqrt{n}$ This is a problem related to cyclotomic polynomial. It is ...
FaranAiki's user avatar
  • 297
1 vote
1 answer
267 views

Finding primitive root modulo 27

I came across a problem regarding primitive roots. It asks to find all primitive roots modulo 27. I know by general theorem, there are $\phi(\phi(27)) = 6$ of them. In order to find them all ...
hmm1's user avatar
  • 53
0 votes
0 answers
60 views

What is the difference between a primitive root mod p and a number with period p-1 mod p where p is prime?

I am currently studying number theory and have come across the idea that that powers of a primitive root generate all nonzero residues in the field $\mathbb{Z}_p$ but I have also seen numbers with a ...
MrMath's user avatar
  • 71
2 votes
1 answer
95 views

tetration primitive root $q \mod p$

Consider primitive roots $q \mod p$ where $q$ is a prime and $p$ is an odd prime $> 5$. I am looking for such pairs $q,p$ such that every residue $a_i \mod p$ is of the form $$a_i = q^{(v_i)} \mod ...
mick's user avatar
  • 16k
1 vote
0 answers
46 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 ...
Wesley's user avatar
  • 11
1 vote
1 answer
147 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 ...
10GeV's user avatar
  • 1,371
2 votes
0 answers
71 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
2 votes
1 answer
52 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 $\...
Gang men's user avatar
  • 425
1 vote
0 answers
274 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 ...
Gang men's user avatar
  • 425
0 votes
0 answers
69 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 ...
Thomas Lipp's user avatar
2 votes
1 answer
105 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'...
ordptt's user avatar
  • 1,039
1 vote
2 answers
69 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 $(...
Mithrandir's user avatar
2 votes
1 answer
147 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 ...
Peter's user avatar
  • 84.6k
0 votes
1 answer
2k 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$ ...
help_pls's user avatar
1 vote
1 answer
813 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 ...
confusedTurtle's user avatar
4 votes
0 answers
157 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 ...
Pranay's user avatar
  • 199
0 votes
0 answers
94 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 ...
HYUN-HO WOO's user avatar
0 votes
0 answers
37 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 ...
Fishboiii's user avatar
4 votes
0 answers
140 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: ...
save123's user avatar
  • 319
1 vote
1 answer
60 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 $\...
carraig's user avatar
  • 557
0 votes
2 answers
162 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 ...
Subham Jaiswal's user avatar
0 votes
1 answer
553 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 ...
quan-dil's user avatar
1 vote
1 answer
42 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$? ...
yuu's user avatar
  • 101
2 votes
1 answer
45 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 ...
Abdelrahman Yousf's user avatar
0 votes
1 answer
47 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^\...
webmathex's user avatar
0 votes
1 answer
127 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 ...
JH07's user avatar
  • 1
1 vote
0 answers
92 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 $...
webmathex's user avatar
0 votes
0 answers
98 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 $...
math110's user avatar
  • 93.4k
0 votes
1 answer
132 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$
Apollo's user avatar
  • 11

1
2 3 4 5
12