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.
581
questions
1
vote
1
answer
99
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 ...
- 83
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 ...
- 29
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
115
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 ...
- 3,045
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,762
0
votes
1
answer
43
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 ...
- 1,109
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.
...
- 61
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$...
user1277306
1
vote
0
answers
41
views
Vinogradov's proof that $U_{p^{\alpha}}$ is cyclic. How to prove $p^{r-1} (p-1) \mid \delta$ for $1 \leq r \leq \alpha$
The proof of Vinogradov that $U_{p^{\alpha}}$ ($\alpha \geq 1$) is cyclic for an odd prime $p$, has a part that I don't understand.
We take $g$ a primitive root of $U_p$.
And, at a certain point of ...
- 1,231
1
vote
4
answers
236
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{...
- 840
2
votes
0
answers
53
views
When does this Galois theorem "variation" holds?
Im reading about solvability by radicals in different books, more concretely in Fields and Galois Theory by Patrick Morandi and Introduction to abstract algebra by Benjamin Fine, etc. In the second ...
- 23
0
votes
1
answer
63
views
Primitive root mod $p^2$ and $p^4$
If $a$ is not a primitive root mod $p^2$ for a prime $p$. What is the fastest way of checking if $a$ is (or it is not) a primitive root mod $p^4$? Is there any useful trick?
Thanks!
- 75
0
votes
1
answer
48
views
Number theory: Where did I go wrong with solving this polynomial congruence? [duplicate]
Question: Find an integer that solves the congruence $$x^{83}\equiv 7 \pmod{139}$$
My working:
Let $b$ denote some primitive root of the prime mod 139, and let $$x\equiv b^y\mod 139$$ for some ...
- 137
0
votes
1
answer
122
views
Check if a polynomial is primitive over a galois field using Magma calculator
I want to check if the polynomial $f(x) = 1 + x^{18} + x^{29} + x^{42} + x^{57} + x^{67} + x^{80}$ is primitive over the Galois Field $GF(2^{80})$ using the Magma Calculator (http://magma.maths.usyd....
