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.

Filter by
Sorted by
Tagged with
0
votes
0answers
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 ...
2
votes
2answers
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. ...
0
votes
1answer
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.) ...
0
votes
1answer
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....
1
vote
1answer
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 (...
0
votes
1answer
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 ...
0
votes
2answers
92 views

Express complex number in terms of radicals

Let $\zeta=\cos(\frac{2\pi}{16})+i\sin(\frac{2\pi}{16})$ be a 16th root of unity, so that it is a primitive root of unity. I need to explicitly express this number in terms of radicals: $a+ib$, where $...
1
vote
0answers
107 views

Are non-squares primitive roots?

We know that even squares cannot be primitive roots modulo primes.Are all other natural numbers primitive roots mod some p? My heuristic argument goes as follows: the probability that a natural ...
1
vote
1answer
158 views

Prove that it is not a primitive root module $p^2$

I don't even know how to start to prove the following... Let $p$ be an odd prime. Prove that if $a$ is a primitive root modulo $p$ then exactly one of the following integers $a,a+p,a+2p,...,a+(p-1)p$...
0
votes
3answers
261 views

For which Mersenne primes and Fermat primes is 2 a primitive root?

Could you help me answering this question? For which Mersenne primes and Fermat primes is 2 a primitive root? I know that a $a$ is a primitive root modulo $n$ if $a$ generates $\mathbb{Z}_n^*$. A ...
2
votes
0answers
250 views

Primitive elements of finite fields

Let $p$ be a prime number and $q=p^n$ for some positive integer $n$. $F_q[x]$ is the polynomial ring with coefficients in $F_q$. For any $M(x)\in F_q[x]$, define $\mathcal{R}(M(x))\subset F_q[x]$ to ...
1
vote
1answer
25 views

Holomorphic function and deritives

Is it true that there exists a holomorphic function whose derivative is $1/(z^2-1)$? How to tackle problems like these?
1
vote
1answer
48 views

Find $\sum_{i=0}^{k-1}w^{in}$ in terms of $n \in \Bbb N$ being $w \in \Bbb C$ a k-th primitive root of unity.

I need some help with the following problem: Find $\sum_{i=0}^{k-1}w^{in}$ in terms of $n \in \Bbb N$ being $w \in \Bbb C$ a k-th primitive root of unity. I thought of writing it as: $\frac{w^{nk}-...
0
votes
1answer
440 views

How to use Hensel lemma to show that primitive root mod $p$ gives primitive root mod $p^2$ of the form $g + tp$

How to use Hensel lemma to show that primitive root mod $p$, where $p$ is prime, gives primitive root mod $p^2$ of the form $g + tp?$ I tried to start with congruence $g^{p-1} \equiv 1 \pmod p,$ so $...
6
votes
2answers
109 views

Question about primitive roots of p and $p^2$

If $g$ is a primitive root of a prime $p$, then $g$ is also a primitive root of $p^2$ if and only if $g^{p-1} \pmod p^2$ is not $1$. Is there a prime $p$ such that $p^2$ missing exactly $m$ primitive ...
11
votes
4answers
6k views

Prove if $n$ has a primitive root, then it has exactly $\phi(\phi(n))$ of them

Prove if $n$ has a primitive root, then it has exactly $\phi(\phi(n))$ of them. Let $a$ be the primitive root then I know other primitive roots will be among $\{a,a^2,a^3 \cdots\cdots a^{\phi(n)} \}$ ...
0
votes
1answer
760 views

Primitive Roots modulo $p^2$ [duplicate]

Prove that if p is a prime then there exist $\ ϕ(ϕ(p^2 )) = (p − 1)ϕ(p − 1)$ primitive roots modulo $p^2.$ I know how to prove the theorem Let p be prime and let d ∈ N be a divisor of p − 1. Then ...
2
votes
1answer
77 views

Show that if ab has a primitive root with $(a,b) = 1$, then $a<3$ or $b<3$

Show that if $ab$ has a primitive root with $\gcd\left(a,b\right) = 1$, then $a<3$ or $b<3$ I have no idea how to start this question at all... One is that I do not see how 3 is related to ...
0
votes
1answer
124 views

Prove that if $g^{(p-1)/2} \equiv -1 (mod \mbox{ } p)$ then its smaller power can't be congruent to 1.

Let $p$ be a prime greater than $2$. Show that $g^{(p-1)/2} \equiv -1 (mod \mbox{ }p)$ implies $g^{k} \not\equiv 1 (mod \mbox{ }p)$ for every $1≤k≤(p-1)/2$.
2
votes
1answer
671 views

Irreducible polynomial, Primitive Polynomial and Minimal Polynomial

I read about irreducible polynomial, primitive polynomial and minimal polynomial and now i am not able to differentiate between them, its chaos in my mind. Can somebody describe what they are actually ...
1
vote
1answer
89 views

Help with problem: Let $w$ a 15th-primitive-root of unity. Find all $n \in \Bbb N_{<0}$ such that $\sum_{i=0}^{n-1} w^{5i}=0$

we are starting to see complex numbers in my algebra class. So I have the following problem: Let $w$ a 15th-primitive-root of unity. Find all $n \in \Bbb N_{<0}$ such that $\sum_{i=0}^{n-1} w^{...
1
vote
4answers
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$...
2
votes
2answers
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 ...
2
votes
3answers
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 ...
1
vote
1answer
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$?
2
votes
2answers
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.
1
vote
1answer
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 ...
1
vote
0answers
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 ...
4
votes
1answer
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 ...
2
votes
2answers
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 ...
2
votes
1answer
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 ...
9
votes
2answers
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 ...
0
votes
1answer
404 views

Proving if $g$ is a primitive root $\pmod n$ and $n$ is prime, then $g^k$ $\pmod n$ is also a primitive root if and only if $\gcd(k, n-1) = 1$

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-...
10
votes
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 "...
0
votes
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 ...
1
vote
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)$...
2
votes
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?$$
2
votes
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 ...
1
vote
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 }\...
0
votes
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 ...
2
votes
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 ...
1
vote
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 ...
0
votes
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 ...
4
votes
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 ...
0
votes
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$.
13
votes
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$ ...
2
votes
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 ...
-3
votes
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 $...
-1
votes
2answers
102 views

Prove that Carmichael number has no primitive roots

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 ...
1
vote
1answer
69 views

Primitive 18-th root of unity problem involving congruences.

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