# 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.

559 questions
Filter by
Sorted by
Tagged with
27 views

### Diagonal patterns in a plot related to Artin's Conjecture about primitive roots

This image displays the following information. The pixel in the ($a$-th row, $k$-th column) is \begin{equation} \begin{cases} \text{gray} & \text{if } a \geq p_k \\ \text{white} & \text{if } a ...
• 17
1 vote
29 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 ...
• 11
1 vote
79 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 ...
• 1,281
33 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 ... 35 views

• 678
37 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 ...
• 80.6k
369 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$ ...
1 vote
108 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 ...
• 85
145 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 ...
• 199
28 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 ...
23 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 ...
134 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: ...
• 299
1 vote
36 views

60 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 ...
• 1
1 vote
80 views

• 91.6k
112 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$
• 11
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 ...
64 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 ...
• 1,554
76 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.
• 91
1 vote
43 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 ...
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,...$ (...
• 405
1 vote
84 views

• 1,646
130 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: ...
• 137
1 vote
137 views

• 269