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
1answer
37 views

Understanding steps of calculating discriminants.

Here is the question I am asking about some steps in its keen answer: For $n =3,$ write $\Delta^2$ as an element of $A = \mathbb{Q}[e_{1}, e_{2}, e_{3}.]$(manually) The answer is given below: What a ...
1
vote
1answer
37 views

Primitive root modulo prime power

If I find $a$ is PR mod p, then a theorem states that either $a$ itself or $a+p$ is the PR mod $p^2$. Is there a fast approach to check the exponents of $a$, instead of going through every element in $...
0
votes
2answers
30 views

Solve congruence for unknown power

QN: Solve $8^x \equiv 3 $ mod 43. I am inspired by the method here: (https://math.stackexchange.com/a/1332788/737799) However there seems to be no solutions in this case. Firstly convert both sides of ...
0
votes
0answers
44 views

Primitive roots mod divisor of an integer

QN: Prove that if there exists a primitive root modulo n, then there exists a primitive root modulo every divisor of n. If $a$ is a primitive root mod n, then $a^{x}\equiv 1$ mod n has least integer ...
0
votes
1answer
25 views

If $p$ is an odd prime with primitive root $1<r<p$, is $r$ also a primitive root modulo $p^2$?

I use excel computed till $p=23$, it's true. But is this always true? if not, could you pls give a counter example?
0
votes
1answer
41 views

Relationships between the Orders of an element in a Cyclic group (multiplicative and additive) Relating to prime numbers

Let p be a prime. Then, we know that $U(\mathbb{F}_p) \simeq \mathbb{Z}/(p-1)\mathbb{Z}$, where $U(\mathbb{F}_p)$ is the group of units of the field $\mathbb{F}_p$. They both have order $p-1$. Given ...
5
votes
1answer
51 views

Existence of primitive root satisfying a certain condition

Let $l$ and $p$ be prime numbers such that $p|l-1$. Suppose there is an integer $r \in \mathbb Z$ such that $r^p \equiv 1 $ mod $l$. Can anyone please help me see why there exists a generator $s$ of $(...
0
votes
1answer
39 views

Do primitive roots mod m always satisfy $\gcd(r^t,m)=1$?

I am confused about primitive roots. My text defines primitive roots as the solutions for $a$ of the equation $\operatorname{ord}_m a = \phi(m)$ where $\operatorname{ord}_m a$ is defined as the ...
1
vote
3answers
43 views

If r is a primitive root mod m, then r is a primitive root $\pmod{\phi(m)}$?

Gerstein's Introduction to Mathematical Structures and Proofs offers the following proposition and corollary: Suppose r is a primitive root mod m: Prop 6.80: $log_r xy \equiv log_r x + log_r y$ ...
1
vote
2answers
31 views

If r is a primitive root, then the residue of $r^t$ is also a primitive root if $\gcd(t,\phi(m))=1$ where $\phi$ is Euler's totient

This is part ii of the proof of Proposition 6.77 of Gerstein's Introduction to Mathematical Structures and Proofs. I don't understand it. Here is how the discussion, and my understanding of it, go: $r$...
1
vote
1answer
42 views

Order of 2 modulo p, where p is a prime divisor of the Fermat number $F_n=2^{2^n}+1$

The order of 2 modulo p is the minimal solution of $2^t\equiv 1 \pmod{p}$ Euler's theorem guarantees that the congruence has a solution. The challenge is to demonstrate that $k=2^{n+1}$ is the minimal ...
3
votes
2answers
74 views

For prime $p \ge 5$ there exists an $n$ with $2 \le n \lt p -1$ with $[n]$ a primitive root of unity of $(\mathbb{Z}/{p^2}\mathbb{Z})^\times$.

Let $p$ be a prime satisfying $p \ge 5$. Is the following true? There exists an integer $n$ satisfying $\quad 2 \le n \lt p -1$ $\quad \text{The residue class } $[n]$ \text{ generates the ...
0
votes
0answers
20 views

Deduction using index calculus to establish the claim

In Christopher Hooley's paper on Artin's Conjecture there is a statement that Index calculus show that for $p \nmid a$ and any prime divisor $q$ of $p-1$ the solubility of the congruence $v^q \equiv ...
3
votes
1answer
76 views

If $p$ is an odd prime and $\alpha\in\Bbb Z/p\Bbb Z^*$, then $\alpha^2$ is not a primitive root modulo $p$.

Prove true or give a counterexample if false. If $p$ is an odd prime and $\alpha\in\Bbb Z/p\Bbb Z^*$, then $\alpha^2$ is not a primitive root modulo $p$. I was trying to prove it to be true, but I ...
1
vote
2answers
37 views

Show that $2$ is a primitive root $\mod{3^k}$ for all positive $k$

Show that $2$ is a primitive root $\mod{3^k}$ for all positive $k$ So in order for $a$ to be a primitive root it would have to satisfy $\text{ord}_{p}a=\phi(p)=p-1$ However here we would have that: $...
1
vote
1answer
50 views

Principal vs primitive $n$-th roots of unity [closed]

Can someone please explain the difference between principal and primitive $n$-th roots of unity ? I know what $n$-th root of unity is but don't seem to understand these two concepts. Can someone ...
0
votes
1answer
35 views

Proving two distinct primitive roots do not generate $\mathbb{Z}^{\times}_n$ in the same order

For any suitable $n$ that has primitive roots (i.e. $n$ of the form $2, 4, p^j, 2p^j$, where $p$ is an odd prime), there exist primitive root(s). In the case that $n$ has more than one primitive root, ...
1
vote
1answer
30 views

Generalization of Artin conjecture to square of primes [closed]

Artin's conjecture on primitive roots states that a given integer a that is neither a perfect square nor −1 is a primitive root modulo infinitely many primes p. Can we expect that it is also a ...
1
vote
0answers
32 views

Prove that $7$ is a primitive root modulo $p=2^s+1$. [duplicate]

I need help with the following question: If $1<s\in \mathbb N$ and $p=2^s+1$ is prime, so $7$ is a primitive root modulo $p$. My thoughts: First I know: $\phi(p)=p-1=2^s$. So if $r$ is the order ...
2
votes
0answers
24 views

Quadratic number fields that contain primitive root of unity

Find all quadratic fields $\mathbb{Q}[\sqrt{d}]$ that contain some $p$-th primitive root of unity, where $p>2$ is a prime. Now, my reasoning was: if $\mathbb{Q}[\sqrt{d}]$ contains one $p$-th root ...
2
votes
0answers
76 views

Is there a deeper reason for the classification of moduli in which a primitive root exists?

The primitive root theorem classifies the set of moduli for which a primitive root exists as $$1,2,4,p^k,2p^k$$ where $p$ is an odd prime and $k$ is a positive integer. I have worked through a proof ...
1
vote
1answer
89 views

Show that $101^2$ does not divide $2^{50}+1$ and that $2$ is a primitive root modulo $101^{101}$

The first task is to show that $101^2$ does not divide $2^{50}+1$. For this I first found out that $2$ is a primitive root modulo $101$, by just looking at the power of $2$. I assume by contrary that $...
1
vote
1answer
42 views

Finding a counter-example for Gaussian-periods for non-primes

I need to give a counter-example against the following theorem: Suppose $H \subset \operatorname{Gal}(\mathbb{Q}(\zeta_n)/\mathbb{Q})$ is a subgroup. Then we have $\mathbb{Q}(\zeta_n)^H = \mathbb{Q}(\...
0
votes
4answers
44 views

For every $k \in \Bbb Z$ there is $0 \le x \le p-1$ such as $x^3\equiv k \pmod {p}$

This question is looking like an easy one but I have been trying to solve it for the last couple days and I haven't been able to prove it - so I need some help. The question: Let $p$ be a prime number,...
1
vote
1answer
65 views

coprime terms in the factorization of $x^p + y^p$

This is a question related to Fermat's last theorem. Let $p\geq5$ be a prime number, and let $\zeta$ be a primitive $p$th root of unity. Consider the Fermat's last theorem: \begin{equation} z^p = (x+y)...
-1
votes
1answer
74 views

Primitive root modulo $2p$

The question: Let $a,p \in \Bbb N$,$ \ $ $p$ is an odd prime, $a$ is a primitive root modulo $p$. prove that: if $a$ is odd, $a$ is primitive root modulo $2p$. if $a$ is even, $a+p$ is primitive root ...
2
votes
1answer
36 views

Prove that $a$ is primitive root modulo $p^2$

I really need to answer this question quickly for my homework due tomorrow: Let $a,p \in \Bbb N$ $p$ is prime, $a$ is a primitive root modulo $p$ that $p^2\nmid (a^{p-1}-1)$. Prove that $a$ is ...
2
votes
1answer
56 views

How to prove that $1^n+2^n+…+(p-1)^n \equiv 0\pmod p$? [duplicate]

I have a homework for the university and I am 'on this' for the entire week, so I really need help. The question: let $p>2$ be a prime number and $n\in \Bbb N$, $\ p-1\nmid n$. Prove that $1^n+2^n+....
0
votes
0answers
89 views

How to show that 2 is primitive root modulo $101^{101}$?

Given the facts: (a) 2 is primitive root modulo 101 (b) $2^{50}+1$ isn't divisible by $101^{2}$ I have been asked to show that 2 is a primitive root modulo $101^{101}$. How do I do that? I started by ...
0
votes
0answers
22 views

All roots of a polynomial in ring $F_2+uF_2+u^2F_2$, where $u^3=0$

Let $R=F_2+uF_2+u^2F_2$, where $u^3=0$, be a finite commutative ring. So $R=\{0,1,u,v,uv,u^2,v^2,v^3\}$, where $v=1+u$, $v^2=1+u^2$, $v^3=1+u+u^2$, $uv=u+u^2$. It is well known that $$x^7-1=(x+v^3)(x^...
0
votes
0answers
50 views

Determine if a $4$-th root of unity is contained in $\mathbb{F}_9$

I have two questions, one of those is the same here, but I'd like to use another argument and I need a check! The text is: i) Is it true that a primitive 3-th root of the unit over $\mathbb{F}_3$ is ...
1
vote
0answers
51 views

Size constraints on reduced solutions to $x^p\equiv 1\mod q$

Are there any size constraints on the reduced solutions $x$, $(0<x<q)$, to $x^p\equiv 1\mod q$, for $p$ and $q$ specific primes? (Considering the primitive $p$-th roots of unity modulo $q$). I ...
0
votes
2answers
19 views

Square root in $\mathbb F_{2^n}$

Let $\mathbb F_{2^n}$ be a finite field with $2^n$ elements. I am just wondering if it is true that for all $n\in \mathbb N$ all elements of $\mathbb F_{2^n}$ have square roots, i.e for all $a\in \...
4
votes
3answers
80 views

Sum of complex roots' fractions

According to this: If $\omega^7 =1$ and $\omega \neq 1$ then find value of $\displaystyle\frac{1}{(\omega+1)^2} + \frac{1}{(\omega^2+1)^2} + \frac{1}{(\omega^3+1)^2} + ... + \frac{1}{(\omega^6+1)^2}=...
0
votes
0answers
30 views

Determine degree min. polynomial

I need a check on the following question Let $\alpha$ a primitive element of $\mathbb{F}_{2^n}$. Determine the degree of the minimal polynomial over $\mathbb{F}_2$. What can you say about the ...
0
votes
0answers
35 views

Smallest field and root of unity

I'm trying to solve the following: Let $K$ be the smallest field, with characteristic $2$ such that it contains a $15$-primitive root of the unit. Find its cardinality and a primitive element of ...
2
votes
1answer
40 views

Minimal extension field of $\mathbb{F}_2$ such that

Find the minimal extension field of $\mathbb{F}_2$ such that this extension contains an element of order $21$? Attempt: I know that such an extension of $\mathbb{F}_2$ is like $\mathbb{F}_{2^s}$ and $...
1
vote
1answer
61 views

Prove that 2 is not a primitive root of any prime of the form $3\cdot 2^n+1$ for $p>13$

I am really struggling with this proof. This doesn't seem like it should be that hard. All I have been trying to do is find a $k<3.2^n$ such that $2^k\equiv 1($mod $ 3\cdot 2^n+1)$, but it turns ...
0
votes
1answer
58 views

How to solve $x^{17}\equiv 37$ in $\mathbb{Z}/101\mathbb{Z}$? [duplicate]

I need to solve the equation $x^{17}\equiv 37$ in $\mathbb{Z}/101\mathbb{Z}$. I've looked into these topics (the calculation of the primitive root is missing, n is not prime) but couldn't derive a ...
0
votes
1answer
32 views

If $m,n,p$ and $m',n',p'$ produce the same Pythagorean triple, does the following have to hold? $m=m'$, $n=n'$ and $p=p'$.

A Pythagorean triple is given by $(x,y,z)=(p(m^2-n^2),p(2mn),p(m^2+n^2))$. Is there a way to show that $m=m'$, $n=n'$ and $p=p'$ or that there's possibly a counterexample where this isn't the case?
0
votes
1answer
28 views

Show that if $m, n$ and $m',n'$ produce the same primitive Pythagorean triple then $m=m'$ and $n=n'.$ [closed]

I have the definition for a primitive PT. If: $m,n$ are positive integers and $m >n$. One of $m,n$ is odd, one is even. $gcm(m,n)=1$ Then $(x,y,z)=((m^2-n^2),2mn,(m^2+n^2))$ is a primitive ...
1
vote
2answers
38 views

Finding all no-congruent primitive roots $\pmod{29}$

Finding all no-congruent primitive roots $\pmod{29}$. I have found that $2$ is a primitve root $\pmod{29}$ Then I found that is it 12 no-congruent roots, since $\varphi(\varphi(29)) = 12$ Then I ...
1
vote
0answers
19 views

How to find an irreducible polynomial over a finite field with a primitive root (and low hamming weight)

I found there that a polynomial in $F[x]$ with $|F| =q $ with degree $n$ will have its roots in $K$ of order $q^n$ Here, I found that either all the roots are primitive or none of them are. I am ...
1
vote
2answers
30 views

Confusion about the choice of primitive root/multiplicative generator in Diffie-Hellman Key Exchange.

I was reading "Jeffrey Hoffstein, Jill Pipher, Joseph H. Silverman, An Introduction to Mathematical Cryptography, Second Edition". I understand the basic Diffie-Hellman Key Exchange. Though, I was ...
0
votes
1answer
29 views

Why is $\alpha$, a primitive pth root of unity, a root of the polynomial $1+t+\ldots +t^{p-1}$?

I'm currently reading a proof that the minimal polynomial of $\alpha$, a primitive pth root of unity, over $\mathbb{Q}$ is $$1+t+\ldots +t^{p-1},$$ yet the author simply states "Clearly $\alpha$ is a ...
-1
votes
1answer
53 views

How do I show that $2$ is not a primitive root modulo $7$? [duplicate]

How do I show that $2$ is not a primitive root modulo $7$? From discrete math. How many times would I need to do the form?
1
vote
3answers
96 views

what is the value of $\binom{n}{1}​+\binom{n}{4}+\binom{n}{7}​+\binom{n}{10}+\binom{n}{13}+\dots$

what is the value of $$\binom{n}{1}​+\binom{n}{4}+\binom{n}{7}​+\binom{n}{10}+\binom{n}{13}+\dots$$ in the form of number, cos, sin attempts : I can calculate the value of $$\binom{n}{0}​+\binom{n}{...
2
votes
1answer
42 views

Given a prime number a of the form 29 (mod 40) or 40k + 29. Show that the prime a cannot divide any integer of the form n^2 + 10.

Not sure how to approach this problem. First idea was proof by contradiction. Assume a divides n^2 + 10 and proceed from there. I couldn't reach a substantial conclusion from this approach.
1
vote
1answer
28 views

Show this congruence holds

I need to show that if $d|p-1$, $d<p-1$ and $g$ is a primitive root modulo $p$ then, $$\sum_{l=1}^{(p-1)/d} g^{dl}\equiv 0\pmod{p}.$$ I have a gut feeling it has something to do with the fact that $...
1
vote
1answer
70 views

Primitive roots as linear combination of a $\mathbb{Q}$-basis of $\mathbb{Q}(\epsilon)$

Let $\epsilon$ be a 9-primitive root of unity I got that the $\mathrm{Irr}(\epsilon,\mathbb{Q})=x^6+x^3+1$ so a $\mathbb{Q}$-basis of $\mathbb{Q}(\epsilon)$ is $\{1,\epsilon,\epsilon^2,\epsilon^3,\...

1
2 3 4 5
10