The Stack Overflow podcast is back! Listen to an interview with our new CEO.

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

412 questions
Filter by
Sorted by
Tagged with
170 views

### Verify that $x$ is a primitive root modulo $n$

I have a question. How can we the quickest to test whether $x$ is a primitive root modulo $n$? On the Wikipedia page I found information about a possible algorithm. This algorithm, however, must ...
671 views

### Why are primitive roots called generators?

I learned recently that the reason that g is commonly used to denote a primitive root is because it stands for "generator". I also know that this has something to do with the non-zero residues. ...
116 views

### Hint for Number Theory question.

I need a hint for this question please: Find the sum of the orders mod 83 over all elements of the set $\{1,2,3,\ldots,82\}$. (If multiple elements have the same order, add that term multiple times.) ...
104 views

### Simple question about generating random primitive roots for a large prime

I am sure this question has been answered before but I could not find any similar question. In Diffie-Hellman protocol implementations we can try to find a large primes using safe prime formula (i.e....
119 views

### Question About Primitive Root of Unity

I stumbled upon one of these exercises in my textbook and thought it would be a great review for my exam. Here is the question: Let $n$ be an odd positive integer, and let $\zeta$ be a primitive (...
196 views

### Find primitive-$n$-th roots of unity over finite field $\mathbb{F}_a$??

Is there efficient methods to find primitive-$n$-th roots of unities over $\mathbb{F}_a$?? In other word, find $\zeta$ such that, $\zeta^n \equiv 1$ where $\zeta \in \mathbb{F}_a$ Also, is there ...
92 views

440 views

510 views

### $m>2$ and $n > 2$ are relatively prime $\Rightarrow$ no primitive root of $mn$

Show that if $m>2$ and $n > 2$ are relatively prime, there is no primitive root of $mn$ I know that $mn > 4$, and thus $\varphi(mn)$ is an even number so that I might write $\varphi(mn) = 2x$...
1k views

### Prove that $r$ is a primitive root modulo $p$ if and only if $r^{(p−1)/q}\not\equiv 1\pmod{p}$

Suppose $p$ is an odd prime. Prove that $r$, with $\gcd(r, p) = 1$, is a primitive root modulo $p$ if and only if $r^{(p−1)/q}\not\equiv 1\pmod{p}$ for all prime divisors $q$ of $p − 1$. The only ...
176 views

### Let $p$ be an odd prime. Suppose that $a$ is an odd integer and also $a$ is a primitive root mod $p$. Show that $a$ is also a primitive root mod $2p$.

Let $p$ be an odd prime. Suppose that $a$ is an odd integer and also $a$ is a primitive root modulo $p$. Show that a is also a primitive root modulo $2p$. Any hints will be appreciated. Thanks very ...
46 views

### Is $g$ mod $p$ a generator for the multiplicative group mod $p^2$?

How would one go about proving/disproving whether $g$, a multiplicative generator mod $p$, is also a multiplicative generator mod $p^2$?
74 views

### Prove that if $r$ is a primitive root modulo $m$, and $(a, m) = (b, m) = 1$, then $r^a \equiv r^b \pmod{m}$ implies $a\equiv b \pmod{\varphi(m)}$

Prove that if $r$ is a primitive root modulo $m$, and $(a, m) = (b, m) = 1$, then $r^a \equiv r^b \pmod{m}$ implies $a \equiv b \pmod{φ(m)}$. Any hints will be appreciated. Thanks so much.
121 views

### Is primitive root or order in number theory relate with order of element in cyclic group?

I just read abstract algebra and found notation of cyclic group (I don't read the whole yet ) the order in number theory state $a^{b}\equiv 1(mod N)$ and Cyclic group state $a^{n}=e$ or I not sure ...
99 views

### Finding primitive root mod n?

in wikipedia, https://en.wikipedia.org/wiki/Primitive_root_modulo_n#Finding_primitive_roots, it says there is no formula to compute primitive root mod n. and in the footnote 8, it seems that there ...
2k views

### Every primitive root modulo an odd prime is a quadratic nonresidue

This is my proof of the title statement. Is it correct? Suppose $a$ is a primitive root and quadratic residue modulo $p$. Then by definition $$\operatorname{ord}_p(a)=p-1$$ But Euler's ...
354 views

### $a$ is a primitive root modulo a prime $p$; $ab\equiv1\bmod p$; prove $b$ is a primitive root modulo $p$

Let $p$ be prime. Prove that if $a$ is a primitive root modulo $p$ and $ab\equiv1\bmod p$, then $b$ is a primitive root modulo $p$. I understand the definition of primitive roots. I am having trouble ...
346 views

### Assuming that $r$ is a primitive root of the odd prime $p$ prove that $r^{(p-1)/2}\equiv -1 \pmod p$ holds

I know if $r$ is primitive root $r^{^{n}}\equiv a\pmod n$ from the set of residue $\{1,2,3....(n-1)\}$ but if change to $r^{(p-1)/2}\equiv -1 \pmod p$. My assumption: It's no longer be primitive ...
20k views

### What are primitive roots modulo n?

I'm trying to understand what primitive roots are for a given $\bmod\ n$. Wolfram's definition is as follows: A primitive root of a prime $p$ is an integer $g$ such that $g\ (\bmod\ p)$ has ...
404 views

Prove that when $n$ is prime, and $g$ is a primitive root $\pmod n$, $g^k$ $\pmod n$ is always a primitive root whenever $\gcd(k, n-1)$ $=$ $1$. Known Facts: It would be the case that if $\gcd(k, n-... 4answers 220 views ### Any element of$\mathbf{Z}[\xi]$is congruent to an integer modulo$(1-\xi)^2$if multiplied by a suitable power of$\xi$I'm currently reading Kummer's famous paper on Fermat's Last Theorem (if anyone wants the link, I'll post it, but the paper is in German). There's the following statement in there, which should be "... 1answer 97 views ### Holomorphic function and primitives I need to prove that$\int_\gamma f'(z)/f(z)dz=0$for any closed curve. It is given that f is holomorphic and satisfies$|f(z)-1|\lt1$in the region. And we can assume$f'(z)$is continuous. I think ... 1answer 287 views ### Primitive element for each subfield of a cyclotomic extension Given an odd prime number$p$, a natural number$r$, and a$p^r-th$primitive root$\zeta=\zeta_p$, I have to find an explicit expression of a primitive element for each subfield of$\mathbb{Q}(\zeta)$... 2answers 99 views ### Is 2 always a primitive root of 3ˣ? That is, is it always that $$2^{3^x}\equiv -1\pmod{3^{x+1}}\large?$$ 1answer 58 views ### Show that a certain set of elements is a basis of the free module$\mathbf{Z}[\xi]$Let$\xi$be a$p$-th root of unity for$p$a prime. It is well-known that$\mathbf{Z}[\xi]$is a free$\mathbb Z$-module. Now I'd like to show that$1, (1-\xi)^2, ..., (1-\xi)^{p-1}$is a basis ... 0answers 53 views ### evaluate the integrals using Primitives Evaluate the integrals$\int_\gamma z^ndz$for all integers n. Here$\gamma$is any circle not containing the origin. The answer to this problem is extremely difficult.$$\int \limits_{\gamma }\... 2answers 266 views ### About Primitive roots Good day! I'm currently studying on the primitive roots mod n. Eventually, I fully understand the concept of calculating the primitive roots of a number by practice, but I encounter the following ... 1answer 60 views ### Discrete logarithm when$\alpha$is not a primitve root When a number$\alpha$is a primitive root for a prime number$n$then$\beta \equiv \alpha^{x} \mod n$can be written as$x = \log_\alpha(\beta) \mod n-1 $. If$n$is not a prime, the equation ... 1answer 492 views ### Proof of$\log_{a}(b_1b_2) = \log_{a}(b_1) + \log_{a}(b_2) $for discrete logarithm? If you have that$a$is a primitive root mod$p$. How can you prove this discrete logarithm property?$\log_{a}(b_1b_2) = \log_{a}(b_1) + \log_{a}(b_2) \pmod{p-1}$I see the proof for the regular ... 1answer 292 views ### Solving$n^{th}$power residue of a congruence I'm given$x^2$≡ -1 mod 365 I know that 365 =$5*73$so then my congruence becomes,$x^2$≡ -1 mod 5 and$x^2$≡ -1 mod 73 Since$(-1)^2$≡ 1 mod 5 and$(-1)^{36}$≡ 1 mod 73 implies that there ... 1answer 183 views ### Count of lower and upper primitive roots of prime$p \equiv 3 \bmod 4$I was exploring the layout of primitive roots of primes over a reasonable range and this question concerns the number of primitive roots either side of$p/2$. Many primes have an exact match between ... 1answer 92 views ### Help with primitive root modulo$p^r$[duplicate] Let$p\ge3$be a prime number,$r$be a natural number and$x$be a primitive root modulo$p^r$. Show that$x$is a primitive root modulo$p$. 1answer 226 views ### Are there infinitely many primes$n$such that$\mathbb{Z}_n^*$is generated by$\{ -1,2 \}$? Let$n$a prime, and let$\mathbb{Z}_n$denote the integers modulo$n$. Let$\mathbb{Z}^*_n$denote the multiplicative group of$\mathbb{Z}_n$Are there infinitely many$n$such that$\mathbb{Z}^*_n$... 1answer 109 views ### A field of Radical Sums I am dealing with a computation that yields numbers that are sums of radicals of the following form:$N=\sum_{i=0}^{m}{a_i\sqrt{b_i}}$Where$a_i,b_i \in \mathbb{Q}$(rationals). The context is ... 1answer 76 views ### Solve$19^n$=$801777482\pmod {4535332489}$given$4535332489$is prime. [closed] Solve$19^n$=$801777482\pmod {4535332489}$given$4535332489$is prime and without calculating any factors of$4535332488$. Is solving this possible with the current information? If so, what is$...
Prove that if $n$ is a Carmichael number, then $n$ has no primitive roots. This seems tricky to prove, and the only logical explanation for this is that it contradicts the basis of the Lucas Primality ...
I have some doubts about this following problem, if you can please try to answer the congruence step: Let $\omega$ be a primitive 18-th root of unity. Find $n \in \mathbb Z$ such that: \$ \omega^n =...