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.
582
questions
1
vote
0
answers
37
views
Inclusion of field extensions $\mathbb{Q}(\omega_p)$ and $\mathbb{Q}(\omega_{2p})$
Could you help me clear up a confusion? Either my following reasoning is wrong, or I should be able to show that $\omega_{2p} \in \mathbb{Q}(\omega_p)$, which does not seem correct.
Degree of Field ...
- 131
1
vote
1
answer
2k
views
Discrete Logarithm Problem
Question: Discrete Logarithm Problem: Let $g$ be a primitive root for $F_{p}$. Suppose that $x = a$ and $x = b$ are both integer solutions to the congruence $g^{x} \equiv h \pmod{p}$. Prove that $a \...
CommunityBot
- 1
3
votes
1
answer
2k
views
Strategy of the proof of every prime number has a primitive root
I am going through number theory from the following book :
https://www.saylor.org/site/wp-content/uploads/2013/05/An-Introductory-in-Elementary-Number-Theory.pdf
On page 96, the proof is given that ...
- 275k
1
vote
1
answer
101
views
distribution of square roots of unity $mod n$ | Factoring with inverse pair
I am writing a proof related to the RSA cryptosystem, specifically showing that given an inverse pair $d, c$ under multiplication mod $\phi(N)$, where
$$ dc \equiv 1 \pmod{\phi(N)}, $$
there exists a ...
- 275k
2
votes
2
answers
1k
views
Primitive roots generated from a primitive root
Let $p$ be a prime number, and let $a$ be a primitive root $\mod p$.
Is it true that $a^m$ is a primitive root if and only if $\gcd(m,p-1)=1$?
One direction is correct: if $a^m$ is a primitive root, ...
CommunityBot
- 1
0
votes
0
answers
44
views
about sum of unity roots
$\zeta_p $ is a primitive $p$-th root of unity in $\mathbb C$.for any $d \in N$, define that $G_d=\Sigma_x(\zeta_p)$^$x^d$, for all $x \in F_p$. Show that the degree over $Q$ of $G_d$ is equal to ...
2
votes
0
answers
60
views
Artin's conjecture on primitive roots for perfect powers
Let $a\neq -1,0,1$ be an integer. Write $a=(b^2c)^k$, where $b^2c$ is not a perfect power, and $c$ is squarefree. Artin's conjecture on primitive roots states that the asymptotic density of the set of ...
- 1,923
4
votes
1
answer
116
views
A question about a proof of Proth's Theorem
This theorem is
The number $N=2^n\cdot k+1$ with $k<2^n$ is prime if and only if there exists $a$ with $a^{(N-1)/2}\equiv -1\mod N$
This proof is
$\Longrightarrow$ :
If $N$ is prime, let $a$ be ...
- 59.2k
3
votes
1
answer
58
views
Two primitive roots add to a third
Primitive roots are useful in analyzing the multiplicative structure of the numbers mod $p$, for $p$ a prime. I wondered if there was anything that could link the multiplicative and additive structure ...
- 4,764
0
votes
1
answer
45
views
Proof of identity on sum of powers of primitive root.
Let $q = p^e$ for some prime $p$. Consider the trace function $\mathrm{Tr}_{\mathbb{F}_q/\mathbb{F}_p}:\mathbb{F}_q\to \mathbb{F}_p$ defined by $\mathrm{Tr}_{\mathbb{F}_q/\mathbb{F}_p}(x) = \sum_{i=0}^...
- 1,011
2
votes
3
answers
134
views
Application of "Every nonzero residue modulo a prime can be represented as a power of a primitive root."
I am reading a machine learning paper, and this paragraph below doesn't quite make sense. How is x+y (mod p−1) and x*y (mod p) equivalent? Suppose p = 5 and x = 3 and y = 4, then clearly 7 mod 4 =3 ...
- 9,399
1
vote
4
answers
238
views
How to find a primitive element for $\mathbb F_{11}$
This is a pretty dumb question considering this is the very first question in my exercises (on a section about finite fields). First, the the group of units $\mathbb F_{11}^*$ is $\mathbb{Z}/10\mathbb{...
- 61.5k
2
votes
1
answer
123
views
Number of zeros in the decimal representation of the powers of 5
I am trying to solve this problem:
Prove that for every natural number $m$, there exists a natural number
$n$ such that in the decimal representation of the number $5^n$ there are at least $m$ zeros.
...
- 5,673
16
votes
2
answers
413
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$ ...
0
votes
0
answers
58
views
The existence of a primitive root
Prove that there exists a primitive root $g$ modulo $p$ ($p$ an odd
prime) such that $g^{p-1}\not\equiv 1 \pmod {p^2}$
So far, I have been able to prove that if $g$ is a primitive root modulo $p$ ($p$...
- 135k