All Questions
Tagged with primitive-roots elementary-number-theory
240
questions
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 ...
- 83
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 ...
- 3,047
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 ...
- 1,119
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
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
50
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
0
answers
33
views
Question about a proof of $\phi(r)$ incongruent integers
Hello I have a particular question, about the proof of the following theorem:
Theorem: If $r|p-1$, with $p$ an odd prime, there are $\phi(r)$ incongruent integers which have order $r$ modulo $p$.
...
- 51
2
votes
0
answers
104
views
Is it possible to create factors of $p_n\#$ which cannot create any primitive root of $p_{n+1}$?
(Edited for clarity.)
Take the primorial of the $n$th prime $p_n$ by using $H=\prod_{i=1}^np_i$.
Does there exist an $n$ such that there exists $d\mid H$ where there are no factors of $d^{p_{n+1}-1}$ ...
- 8,145
0
votes
1
answer
87
views
Let p be a prime number with p≡3 (mod 4) and let r be a primitive root modulo p . Prove that $\mathrm{ord}_p(-r) = (p-1)/2.$
I only could write this:
Let p = 4k + 3 where k is an nonnegative integer.
Since r is a primitive root modulo p .
$r^{(p-1)/2} ≡ - 1 $ mod p. So
$r^{2k+1}≡ -1$ mod p
$(-r)^{2k+1}=-1*(r)^{2k+1}$
$-1*(...
- 3
0
votes
1
answer
84
views
I've some problem in the definition of primitive root in the Discrete Mathematics and Its Applications [duplicate]
In the book, he said that "A primitive root modulo a prime p is an integer r in $\mathbb Z_p$ such that every nonzero element of $\mathbb Z_p$ is a power of r."
It is very different to other ...
- 53