Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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.

2
votes
2answers
475 views

Proof of Fermat's Little Theorem using Primitive Roots

I just learned about primitive roots today, and then I thought of this proof of Fermat's Little Theorem. Seeing that most proofs of this theorem aren't simple, I think I'm either completely wrong in ...
1
vote
0answers
79 views

Multiplicative order: an exercise

I've got this problem: Determine an integer with (exactly) multiplicative order $22$ mod $1331$ Is there a general way to procede in any case with this kind of exercises? Thank you!
2
votes
1answer
79 views

If $g$ is a primitive root, show that $a$ is a $d$th power $\iff$ $a\equiv g^{kd}$

I wanted to ask you to help me with this exercise in numer theory. Here it is: If $g$ is a primitive root modulo $p$ and $d|p-1$, show that $g^{(p-1)/d}$ has order $d$. Show also that $a$ is a $d$...
5
votes
2answers
455 views

Primitive roots modulo n

How do I find a primitive root for a given $n$? For which $n$ does a primitive root exist (I would have guessed it's for all $n$ which are not divisible by 8)? Is there a systematic way, to constuct ...
2
votes
1answer
87 views

suppose a>1 is an integer, and p is an odd prime number.

Suppose $a>1$ is an integer, and $p$ is an odd prime number. Prove that each odd prime factor of $(a^p)-1$ which does not divide $a-1$ should be in the form $2pt+1$. My Approaching: ($a^p)-1$ is ...
0
votes
1answer
48 views

Prove or Disprove the following statemnet

Prove or Disprove the following statement: For each integer n>1 and each divisor d of φ(n), there is an integer a of order d modulo n. Any help would be appreciated.
0
votes
1answer
141 views

if $b^k$ is a primitive root, then $b$ is a primitive root

Any hints or strategies would be greatly appreciated: If $m$ is an integer and $b^k$ is a primitive root mod $m$, then $b$ is a primitive root mod $m$. I am reviewing material from my elementary ...
5
votes
1answer
3k views

Proof of existence of primitive roots

In my book (Elementary Number Theory, Stillwell), exercise 3.9.1 asks to give an alternative proof of the existence of a primitive root for any prime. Let $p$ be prime, and consider the group $\...
1
vote
2answers
1k views

Solve congruence with primitive root

I am seeking the solution to the congruence $$ 29x^{33} \equiv 27\ \text{(mod 11)} $$ Primitive root is 2 and $ord_{11} (2) =10$. Then I got so the equation can be field: $$ lnd_2(29) + 33 lnd_2(...
9
votes
2answers
19k 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
33 views

Give a list of all the numbers $n$ such that $n$ has a primitive root

Is there a way of generalizing all the numbers that have primitive roots?
1
vote
1answer
119 views

Primitive roots used to work out $x^7 \equiv 5 \pmod {11}$

I have a workbook question that doesn't have any example solution, that is as follows: Primitive roots used to work out $x^7 \equiv 5 \pmod {11}$ Now I can see $\phi(11)=10$ and $2$ has order $10$ ...
1
vote
1answer
662 views

Why must a primitive root be less than and relatively prime to n?

"For instance there are no primitive roots modulo 8. To see this note that the only integers less than 8 and relatively prime to 8 are 1, 3, 5, and 7..." The author then proceeds to show that the ...
1
vote
1answer
459 views

Diffie–Hellman key exchange

Today I have learned about primitive roots, as part of my study about Diffie-Hellman, This is the formula: G(generator), P(prime), A(side A), B(side B) A = G^A MOD P B = G^B MOD P AS is a secret ...
2
votes
2answers
1k views

Prove that 3 is a primitive root of $7^k$ for all $k \ge 1$

so I am trying to find out how to prove that 3 is a primitive root of $7^k$ for all $k \ge 1$. I am trying to prove this via induction. Thanks.
1
vote
0answers
693 views

Extension field of F2 , expressing roots and primitive elements in that field

Let $\Phi$ be an extension field of $\Bbb{F}_2$ of extension degree s >1. Let $a(x)$ be a non-zero polynomial with the coefficients in $\Bbb{F}_2$. (a) Show that if $\beta$ is a root of the ...
0
votes
2answers
126 views

Why arcsinh$(x)$ is the primitive of $(x^2+1)^{-1/2}$

I have a question: How to calculate the following primitive of $g(x)$. $I=\int g(x)\text{d}x=\int\dfrac{\text{d}x}{\sqrt{x^2+1}}$. I know that it is equal to the inverse of the sinus hyperbolic ...
3
votes
3answers
577 views

No primitive root modulo $2^n$ for $n\ge 3$

Prove that there is no primitive root modulo $2^n$. I'm not sure how to begin proving this. I know $\varphi(2^n)=2^{n-1}$, thus a primitive root $a\in\left(\dfrac{\mathbb{Z}}{2^n\mathbb{Z}}\right)^*$ ...
0
votes
3answers
93 views

How do I primitive $\sin(x)\cos^3(x)$ step by step?

I tried to primitive $\sin(x)\cos^3(x)$ step be step, but I got stuck. Can I use substitution? $[\sin(x)]' = \cos(x)$ And write $\cos^3$ as $\cos^2(x)*\cos(x)$ And also write the function $\sin(x)\...
1
vote
2answers
186 views

Finding all solutions to $3^x \equiv 9 \pmod{13}$

Find all solutions to $3^x \equiv 9 \pmod{13}$. I don't know how to solve this problem. $3$ is a primitive root for $\mod{13}$ but the solution uses $2$ as a primitive root. Why can't I use $3$? Is ...
2
votes
1answer
676 views

Primitive roots and Legendre symbol

One knows that if $a$ is a primitive root modulo $p$, then $(\frac{a}{p})=-1$. Thus, if $(\frac{a}{p})=1$ we know that $a$ is not a primitive root modulo $p$. Are there any other properties between ...
2
votes
2answers
190 views

Primitive Roots modulo p

I'm asked the following question: Prove that $b$ is a primitive root modulo $p \implies$ the smallest positive exponent $e$ such that $b^e \equiv 1 \pmod p$ is $p - 1$. I know that this could ...
6
votes
2answers
319 views

Show that $-3$ is a primitive root modulo $p=2q+1$

This was a question from an exam: Let $q \ge 5$ be a prime number and assume that $p=2q+1$ is also prime. Prove that $-3$ is a primitive root in $\mathbb{Z}_p$. I guess the solution goes something ...
9
votes
2answers
1k views

Is every non-square integer a primitive root modulo some odd prime?

This question often comes in my mind when doing exercices in elementary number theory: Is every non-square integer a primitive root modulo some odd prime? This would make many exercices much ...
1
vote
1answer
129 views

Primitive roots and Discrete logarithms question

Can anyone help me solve this previous exam question?
4
votes
2answers
237 views

2 is a primitive root mod $3^h$ for any positive integer $h$

It's easy to verify that 2 is a primitive root mod $3^2$. But then why does it follow that 2 is a primitive root mod $3^h$ for any positive integer $h$? This was used in the solution of 2009 Putnam ...
2
votes
2answers
1k views

Prove that if g is a primitive root modulo p (p is an odd prime), then g belongs to h modulo $p^m$, where $h=(p-1)p^r$ for some r.

Prove that if g is a primitive root modulo p (p is an odd prime), then g belongs to h modulo $p^m$, where $h=(p-1)p^r$ for some r. I know if $g^k \equiv a\pmod{p}$, then $g^k \equiv a\pmod{p^m}$, but ...
3
votes
2answers
4k views

Relationship between primitive roots and quadratic residues

I understand that if $g$ is a primitive root modulo an odd prime $p$, then Euler's Criterion tells us that $g$ cannot be a quadratic residue. My question is, does this result generalize to prime ...
4
votes
2answers
1k views

integer $m$ has primitive root if and only if the only solutions of the congruence $x^{2} \equiv 1 \pmod m$ are $x \equiv \pm 1\pmod m$.

Show that the integer $m$ has primitive root if and only if the only solutions of the congruence $x^{2} \equiv 1 \pmod m$ are $x \equiv \pm 1\pmod m$. I don't quite understand what this question is ...
1
vote
2answers
967 views

Primitive Roots Proofs

I am stuck on how to prove these two questions: (1) Let r be a primitive root of the prime $p$ with $p$ congruent to $1$ modulo $4$. Show that $-r$ is also a primitive root. (2) Let n be a positive ...
1
vote
1answer
50 views

Prove that if $2^{4\times5^k}=x\times5^{k+3}+a,0<a<5^{k+3},$ then $5\mid x$

Let $$2^{4\times5^k}\equiv a \pmod {5^{k+3}},\\2^{4\times5^k}\equiv b \pmod {5^{k+4}},$$ and $0<a<5^{k+3},0<b<5^{k+4},$ prove that $a=b.$$(k>1)$ This is equivalent to this: if $2^{4\...
1
vote
1answer
320 views

Primitive Root Proof [closed]

What are the proofs for the following: Let $p$ and $q$ be odd prime numbers with $q=2p+1.$ (a) Prove that $-4$ is a primitive root modulo $q$. (b) If $p\equiv 1\pmod 4$, prove that $2$ is a ...
1
vote
2answers
1k views

Proofs with primitive roots

Please prove the following: Let m be a positive integer a) If a primitive root modulo m exists, prove that the product of all positive integers not exceeding m and relatively prime to m is congruent ...
5
votes
1answer
740 views

Sums of Primitive Roots and Quadratic Residues when $p \equiv 3\pmod 4$

Define $$R_{p}=\{ r \mid r: \text{primitive root of p}, 1 \le r \le p \}$$ and also $$Q_{p}=\{ a \mid a: \text{quadratic residue of p}, 1 \le a \le p \}$$ $$Q_p^c=\{a \mid a: \text{...
1
vote
1answer
638 views

Number Theory Help: Eulers phi function, LCM, and Modulos

Assume that $r$ and $s$ are relatively prime positive integers and that $n =rs$. Let $m = \mbox{lcm}(\phi(s), \phi(r))$ and assume that $\mbox{gcd}(a,n)=1$. Prove $$a^m \equiv 1 \bmod{r} \mbox{ ...
1
vote
1answer
283 views

Show that $α^k$ is also a primitive element if and only if gcd$(k, q − 1) = 1$.

Let $α$ be a primitive element of $F_q$ . Show that $α^k$ is also a primitive element if and only if gcd$(k, q − 1) = 1$. $1=ak+b(q-1) \implies α^1=α^{(ak+b(q-1))}=α^{(ak)}α^{(q-1)}a=α^ka=α$ i cant ...
0
votes
1answer
213 views

Primitive Root Modulo $m$

I need help with the following: Show that if $b$ is a primitive root modulo $m$, then $$\{b,b^2,b^3,...,b^m-1\}$$ is a complete set of units modulo $m$.
0
votes
1answer
720 views

Primitives and minimal polynomials

got this assignment from my coding class and don't know if I've made it correct. Can someone tell if my methods for solving the tasks are correct? Let $f(x) = 1 + x ^3 + x ^4$ . It is given that $f(x)...
0
votes
1answer
403 views

Counting Primtive Roots modulo a prime with Totient Function

Let $\psi: \mathbb{N}^+ \rightarrow \mathbb{N}^+$ be the Totient function which counts the number of positive integers coprime to its argument. Let $p$ be a prime number. Then the number of ...
2
votes
1answer
342 views

primitive roots of primes exercise ( is related to Sophie German theorem)

Let p and q be primes with $q\gt p$ such that p is not a factor of q-1. As q is a prime, we know that for any integer x we can write $x^{q-1}$ in the form $x^{q-1} = kq+1$ for some integer k. ...
11
votes
4answers
5k 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)} \}$ ...
13
votes
3answers
3k views

Prove sum of primitive roots congruent to $\mu(p-1) \pmod{p}$

Suppose that $p$ is a prime. Prove that the sum of the primitive roots modulo $p$ is congruent to $\mu(p − 1) \pmod{p}$.