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.

410 questions
Filter by
Sorted by
Tagged with
107 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 ...
75 views

Distribution of primitive roots mod p

Let $p$ be a prime number. I am interested in knowing how many primitive roots mod $p$ there are; at least, gaining some insight into the distribution of primitive roots mod $p$. If I need to go ...
46 views

Prove that there are exactly $\phi(p-1)$ primitive roots modulo a prime $p$

Note, in the proof below, I assume as proven the theorem that, if $d$ is any factor of $p-1$, then the equation $$\tag{1} x^d -1\equiv 0\pmod{p}$$ has exactly $d$ solutions, and I skip the details of ...
25 views

Product of the primitive roots

If $p$ is a prime number, what is the product of elements like $g$ such that $1\le g\le p^2$ and $g$ is a primitive root modulo $p$ but it's not a primitive root modulo $p^2$? I am interested in the ...
53 views

What are the chances of common generators? [closed]

Supposing $n=\prod_{i=1}^tp_i$ is odd and may not be square-free and $g$ generates each of multiplicative groups mod $\lambda(p_i)$ then what are the chances that $g$ generates multiplicative group ...
25 views

87 views

Why is $[\mathbb{Q}(\zeta):\mathbb{Q}] = 8$ and not $14$? (Where $\zeta$ is a primitive $15^{th}$ root of unity)

I have a field extension $\mathbb{Q}(\zeta)/\mathbb{Q}$, where $\zeta$ is a primitive $15^{th}$ root of unity. So, since $x^{15}-1 = \phi_{1}(x)\phi_{3}(x)\phi_{5}(x)\phi_{15}(x)$, where $\phi_{n}(x)$...
51 views

50 views

$\zeta_n^k$ is primitive if and only if $(k,n) = 1$ [duplicate]

Show that for $k \in \mathbb{Z}$: Is $\zeta_n$ a primitive $n$-th root of unity, then $\zeta_n^k$ is primitive if and only if $(k,n) = 1$. I only need the backwards direction: $\zeta_n^k$ is ...
40 views

$(e^{2\pi i}){}^n \neq e^{2\pi i n}$ where $n\in\mathbb{N}$?

When I type these equations into a calculator I get $({e^{2\pi i}}){}^n = 1$ and something else for $e^{2\pi i n}$. Is that due to the imprecision of the calculator or does the inequality follow ...
Primes $p$ in which $3$ is a primitive root modulo $p$ [duplicate]
I want to show that if $3$ is a primitive root modulo $p$ if $p$ is a prime of the form $2^n+1$ for some $n>1$. First, I wrote $3^{p-1} \equiv 1 \mod p$. Then writing it as $(1+2)^{p-1}$, we see ...
Which primes divide $x^2-5$?
Which primes divide $x^2-5$? What I have tried: If $p$ divides $x^2 -5$ then: $$x^2= 5\pmod{p}$$ Therefore, from Euler's extended theorem we get that for primes s.t $\gcd(5,p)=1$ (which are all ...