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
2 votes
1 answer
114 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
55 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 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,141
1 vote
4 answers
205 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
51 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
62 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
46 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
104 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
56 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,115
0 votes
1 answer
58 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
81 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
235 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
93 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
  • 15.9k
1 vote
0 answers
43 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
141 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,331
2 votes
0 answers
64 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
49 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
220 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
101 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
67 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
124 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
  • 83.7k
0 votes
1 answer
1k 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
601 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
87 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
36 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
139 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
58 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
147 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
499 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
41 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
44 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
45 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
85 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
90 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
91 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.2k
0 votes
1 answer
131 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
-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 ...
Jejouze's user avatar
0 votes
1 answer
68 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 ...
Eldar Sultanow's user avatar
0 votes
1 answer
88 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.
Dodomol's user avatar
  • 103
1 vote
0 answers
48 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 ...
thomasmaths's user avatar
4 votes
0 answers
61 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,...$ (...
T. Rex's user avatar
  • 405
1 vote
0 answers
131 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^...
Willtswhite's user avatar

1
2 3 4 5
12