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
2
votes
1answer
90 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
49 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
201 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 ...
6
votes
1answer
4k 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
2k 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(...
11
votes
2answers
24k 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
35 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
142 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
821 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
548 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 key ...
2
votes
2answers
2k 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
876 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
138 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
811 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
98 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
218 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
874 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
251 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
358 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 ...
11
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
153 views

Primitive roots and Discrete logarithms question

Can anyone help me solve this previous exam question?
4
votes
3answers
496 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
3answers
2k 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 ...
4
votes
2answers
5k 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
2k 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 ...
2
votes
2answers
1k 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
52 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
378 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 ...
5
votes
1answer
958 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
771 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
354 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 ...
2
votes
1answer
229 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
772 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
466 views

Counting Primitive 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
376 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. ...
12
votes
4answers
7k 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
4k 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}$.

1
6 7 8 9
10