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
1 answer
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 ...
user avatar
-2 votes
0 answers
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 ...
user avatar
  • 1,545
-1 votes
0 answers
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 ...
user avatar
0 votes
0 answers
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$...
user avatar
  • 160
1 vote
1 answer
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$? ...
user avatar
  • 101
2 votes
1 answer
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 ...
user avatar
0 votes
1 answer
34 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^\...
user avatar
0 votes
1 answer
46 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 ...
user avatar
  • 1
1 vote
0 answers
73 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 $...
user avatar
0 votes
0 answers
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.
user avatar
0 votes
0 answers
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$ ...
user avatar
0 votes
0 answers
43 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 $...
user avatar
0 votes
1 answer
61 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$
user avatar
  • 11
-4 votes
2 answers
54 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 ...
user avatar
0 votes
1 answer
59 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 ...
user avatar
0 votes
1 answer
70 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.
user avatar
  • 83
1 vote
0 answers
42 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 ...
user avatar
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,...$ (...
user avatar
  • 181
0 votes
0 answers
21 views

Finding integers a between 1 and 19 such that the congruence has a solution

I know that 2 is a primitive root of 19. How do I try to solve this problem?
user avatar
1 vote
0 answers
53 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^...
user avatar
4 votes
1 answer
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 ...
user avatar
  • 16.8k
0 votes
0 answers
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 ...
user avatar
  • 13
0 votes
0 answers
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: $${...
user avatar
0 votes
0 answers
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 ...
user avatar
  • 137
2 votes
0 answers
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 ...
user avatar
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 ...
user avatar
  • 1,544
3 votes
1 answer
88 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: ...
user avatar
  • 137
0 votes
1 answer
106 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, \...
user avatar
  • 121
4 votes
0 answers
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 '...
user avatar
  • 7,562
3 votes
1 answer
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 ...
user avatar
  • 1,197
2 votes
1 answer
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 ...
user avatar
  • 589
0 votes
0 answers
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)$, ...
user avatar
1 vote
0 answers
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 ...
user avatar
-2 votes
1 answer
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 ...
user avatar
  • 21
1 vote
1 answer
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$, ...
user avatar
0 votes
0 answers
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 ...
user avatar
  • 261
0 votes
1 answer
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 ...
user avatar
  • 3
1 vote
0 answers
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 ...
user avatar
0 votes
0 answers
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 ...
user avatar
3 votes
1 answer
111 views

Primitive roots modulo odd prime p

For an odd prime $p$, show that: (a) Any primitive root of $p^2$ is also a primitive root of $p$ (b) Any primitive root of $p^n$ is also a primitive root of $p$ For part (a): $r$ is a primitive root $...
user avatar
  • 113
-4 votes
3 answers
97 views

How to solve $x^3 = 3$ (mod $257)$ while knowing that $3$ is a primitive root mod $257$? [closed]

We were given the hint that $3$ is a primitive root of unity, meaning that for all $y$ such that $\gcd(y,257)=1$, we can find a power $k$ such that $3^k \equiv y$ (mod $257)$. But I have no idea how ...
user avatar
  • 2,869
0 votes
1 answer
349 views

which Numbers can have primitive roots? [duplicate]

I know that if $(a,n)=1,n>0$ and $a^{ϕ(n)}≡1\pmod n$, i.e, order of a $\bmod n$ is $ϕ(n)$, then $a$ is called the primitive root modulo $n$. I want to know what are the possible values of $n$, i....
user avatar
2 votes
3 answers
83 views

Writing Moduler Exponentiation In Terms Of Other Roots (Related To Primitive Roots?)

First, I am not a mathematician; my highest math courses were undergrad linear algebra and ODEs a decade ago, plus some additional learning on my own since then. I welcome correction on my terminology ...
user avatar
1 vote
0 answers
47 views

Some problems on primitive roots and divisors in number theory.

I have two questions: Let $n>1$ be a positive integer that isn't a perfect power. Is $n$ a generator mod infinitely many primes? Let $C,x,y$ be pairwise coprime integers $\in \mathbb{N}$. Let $...
user avatar
  • 130
1 vote
0 answers
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 ...
user avatar
1 vote
0 answers
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 ...
user avatar
1 vote
1 answer
51 views

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 ...
user avatar
  • 1,406
2 votes
0 answers
116 views

Show that 1/p has period p-1 iff 10 is a primitive root mod p

I have this excersice, and i want verify my proof: Let $p$ be a prime, then $1/p$ has period $p-1$ iff 10 is a primitive root $\mod p$. My attempt: $\rightarrow)$ Let $\frac{1}{p}=0,\overline{a_1\...
user avatar
2 votes
0 answers
132 views

Problem involving primitive root mod prime [closed]

For positive integers $n$, let $s(n)$ be the sum of $n$-th powers of primitive roots $\bmod 1601$. Find the number of positive integers $n < 1000$ such that $1601$ divides $s(n)$. How do I approach ...
user avatar
0 votes
1 answer
59 views

Artin's conjecture on a function field

Artin's conjecture states that if $a\ne -1$ and $a$ isn't a perfect square, then $a$ is a primitive root for infinitely many primes $p$. There's an analogue conjecture for function fields but what is ...
user avatar
  • 1

1
2 3 4 5
11