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.

548 questions
Filter by
Sorted by
Tagged with
86 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 ...
63 views

Primitive root and prime $p'$ such that $4p' +1$ is also a prime [closed]

The following question is from my assignment in number theory and I am not able to make any progress on this. I have been following Elementary number theory by David Burton. If $p$ is a prime of the ...
• 1,545
26 views

Is $g^{\phi(n)/2}$ always equal to $\pm 1 \pmod{n}$ for coprime g and n? [duplicate]

I looked at the primitive root check optimization where they suggest to check for a $g$ (candidate) coprime with $n$ that $g^{\phi(n)/2} \not\equiv 1 \pmod{p}$ first, rejecting the candidates ...
40 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
27 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
36 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 ...
34 views

18 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.
20 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$ ...
43 views

40 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 ...
• 16.8k
39 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
52 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: {...
25 views

Powers of full repetend primes in finding the longest period

For $n \in (7,20000)$, $x < n$ is such that $\forall y<n \text{, period} \frac{1}{x} > \text{period} \frac{1}{y}$. Then $x$ is either a full repetend prime, or a full repetend prime to the ...
• 137
81 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,007
67 views

• 121
81 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,562
97 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 ...
• 1,197
82 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 ...
• 589
99 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
77 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,151
168 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
86 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$, ...
99 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 ...
• 261
109 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 ...
1 vote
56 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 ...
40 views

What is the connection between a complete set of reduced residues modulo n and the number of primitive roots to n?

Hi I am trying to understand the proofs regarding number of primitive roots. I have tried many sources, but they all start basically the same without any justification. Maybe it is just me who is not ...
111 views

• 130
1 vote
73 views

A Primitive element in Finite Fields

My question is about the roots of unity in finite fields. It goes like this: Suppose we have two primes p and q, both greater than 3, which satisfy $q|(p-1)$. Then there exists a $q$-the root of unity ...
• 173
1 vote
72 views

How can these two arguments relate?

I found the excerpt here that said the second involves the p-adic analog of the above. How can these two statement related? The transcendence of $2^{\sqrt2}$ and $e^\pi$: Gelfand's proof. (Assuming ...
1 vote
Prove that $g^{p^{v-1}}(1+p) \bmod p^v$ has order $p^v-p^{v-1}$
Let $p$ be an odd prime and $v\geq 2$ Prove that if $g\bmod p$ has order $p-1$ in $\mathbb{Z}/p\mathbb{Z}$, then $g^{p^{v-1}}(1+p) \bmod p^v$ has order $p^v-p^{v-1}$ in $\mathbb{Z}/p^v\mathbb{Z}$ I ...