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.

582 questions
Filter by
Sorted by
Tagged with
44 views

$\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 ...
• 29
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 ...
• 1,779
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 ...
• 2,464
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 ...
• 4,622
42 views

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 ...
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!
• 75
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 ...
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....
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$. ...
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 ...
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}$ ...
• 8,125
65 views

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 ...
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?...
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 ...
• 297
1 vote
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 ...
• 53
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 ...
• 71
95 views

• 1,039
1 vote
69 views

• 557
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 ...
• 3,613
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 ...
1 vote
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$? ...
• 101
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 ...