Skip to main content
16 votes

If $p$ is an odd prime and $k$ an integer with $0<k<p-1$ then $1^k + 2^k + \ldots + (p-1)^k$ is divisible by $p$

Below are six alternative approaches: First, let $a$ be a number such that $\gcd(a,p)=1$ and $a^k\not\equiv1\pmod p,$ which exists as $k<p-1.$ Then denote the sum as $S:=\sum\limits_{l=1}^{p-1}l^...
awllower's user avatar
  • 16.6k
10 votes
Accepted

Strategy of the proof of every prime number has a primitive root

While I'm still not quite sure what you're asking, I shall go through each section of the proof in a lot of detail with the hope that this will help. Again, I'm sorry if I go over a lot of things you ...
Isky Mathews's user avatar
  • 3,285
7 votes
Accepted

If $p$ is an odd prime and $k$ an integer with $0<k<p-1$ then $1^k + 2^k + \ldots + (p-1)^k$ is divisible by $p$

Let $g$ be a primitive root of $p$, and let $S_k$ be our sum. Note that $g,g^2,g^3,\dots, g^{p-2}$ travel in some order, modulo $p$, through the numbers $2$ to $p-1$. It follows that $$S_k=1^k+2^k+3^k+...
André Nicolas's user avatar
7 votes

Distribution of Primitive Elements Finite Fields Prime Order

Gauss proved that the sum $S_p$ of all primitive roots modulo $p$ in the interval $[1,p-1]$ is congruent to $\mu(p-1)$ modulo $p$. This result appeared several times before in MSE and a possible proof ...
Sungjin Kim's user avatar
  • 20.3k
7 votes
Accepted

Any element of $\mathbf{Z}[\xi]$ is congruent to an integer modulo $(1-\xi)^2$ if multiplied by a suitable power of $\xi$

This is false - $ 1 - \xi $ can never be multiplied by a power of $ \xi $ to be an integer modulo $ (1 - \xi)^2 $. Let $ \mathfrak p = (1 - \xi) $ throughout the post. To see this, note that $ p \...
Ege Erdil's user avatar
  • 17.8k
7 votes

Any element of $\mathbf{Z}[\xi]$ is congruent to an integer modulo $(1-\xi)^2$ if multiplied by a suitable power of $\xi$

Perhaps you dropped some hypothesis in your statement, which should be: "Any unit $u$ in $\mathbf Z[\zeta]$ can be multiplied, etc." By Dirichlet's unit theorem (or by direct computation), $u$ is of ...
nguyen quang do's user avatar
7 votes
Accepted

Primitive Root Theorem Proof

Note that the relevant number theory term is "primitive root", which is a generator of the cyclic group $U(n)$ when that group is indeed cyclic. The general outline of establishing which moduli have ...
Greg Martin's user avatar
  • 81.9k
7 votes
Accepted

Show $2+\alpha$ is a primitive root of $\mathbb{F}_{25}$.

Suppose that $2+\alpha$ is not a primitive root; then its multiplicative order is a proper divisor of $24$, so it divides either $8$ or $12$. Compute $(2+\alpha)^8$ and $(2+\alpha)^{12}$. It helps to ...
Servaes's user avatar
  • 64k
7 votes
Accepted

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

The degree of a field extension of the form $\mathbb{Q}(\alpha)$ is the degree of the minimal polynomial of $\alpha$, i.e. the degree of a monic irreducible polynomial of which $\alpha$ is a root. The ...
hunter's user avatar
  • 31.3k
6 votes
Accepted

Every primitive root modulo an odd prime is a quadratic nonresidue

Using Euler's criterion might be correct but seems a little overpowered. You could fairly easily achieve the result by assuming that $a$ is a quadratic residue and then considering the order of $b$ (...
Joffan's user avatar
  • 39.9k
6 votes
Accepted

simplify a numerical expression without calculator

$2017^2=(2018-1)^2=2018^2-2\cdot2018+1$, $2019^2=(2018+1)^2=2018^2+2\cdot2018+1$, You deduce that $2017^2-2018^2+2019^2=2018^2-2\cdot2018+1-2018^2+2018^2+2\cdot2018+1=2018^2+2$
Tsemo Aristide's user avatar
6 votes
Accepted

Let $w$ be a primitive root of a unit of order 3, prove that $(1-w+w^2)(1+w-w^2)=4$

Note that $w^3=1$ and $1+w+w^2=0$ $$=(1-w+w^2)(1+w-w^2)$$ $1+w^2=-w$ and $1+w=-w^2$ $$=(-w-w)(-w^2-w^2)$$ $$=(2w)(2w^2)$$ $$=4w^3$$ $$=4(1)=4$$
tien lee's user avatar
  • 1,773
5 votes
Accepted

Determine every degree 4 primitive polynomial in $GF(2)[x]$

To show that $f = x^{4} + x + 1$ is primitive, first of all check it is irreducible. (You may skip this, see below.) You will want to show that it has no roots in $GF(2)$ (so it has no factor of ...
Andreas Caranti's user avatar
5 votes

How to find a primitive root modulo $5^{10}$?

Find a primitive root mod $5$. I notice $3$ is a primitive root mod $5$. Either $3$ or $3 + 5 = 8$ will be a primitive root mod $25$. A quick check shows that $3$ is still a primitive root mod $25$. ...
davidlowryduda's user avatar
  • 92.5k
5 votes

Find a primitive root of $71$.

$G=\mathbb{Z}/(71\mathbb{Z})^*$ is a cyclic group with order $70=2\cdot 5\cdot 7$. It follows that any $g\in G$ such that $g^{10}\not\equiv 1\pmod{71}$, $g^{14}\not\equiv 1\pmod{71}$ and $g^{35}\not\...
Jack D'Aurizio's user avatar
5 votes
Accepted

Primitive Roots mod a prime number

Hint: $$g^{(p-1)/2}\equiv h^{(p-1)/2}\equiv-1\pmod p$$ $$(gh)^{(p-1)/2}\equiv?$$
lab bhattacharjee's user avatar
5 votes

Show $2+\alpha$ is a primitive root of $\mathbb{F}_{25}$.

I can't resist pointing out the following alternative that in a way allows us to use Moivre's formula here. Observe that in $\Bbb{F}_5$ we have $2=-3$. Therefore $$ z=2+\alpha=-3+\sqrt{-3}=-3+ i\...
Jyrki Lahtonen's user avatar
5 votes
Accepted

Sum of powers mod p

To elaborate on my comment: Suppose that $p-1\nmid n$. Then let $g$ be a primitive root $\pmod p$. It follows that $g^n\not \equiv 1 \pmod p$. Also, $g$ is clearly invertible $\pmod p$. That ...
lulu's user avatar
  • 71.7k
5 votes
Accepted

Distribution of primitive roots mod p

One can certainly find integers $n$ with $$\frac{\varphi(n)}{n} \sim \frac{e^{-\gamma}}{\log \log(n)}$$ (for example, the product of the first $k$ primes), and this is best possible. By Dirichlet's ...
user708710's user avatar
4 votes

Find the number of solutions of $x^k\equiv 45\pmod{97}$

If $G$ is a cyclic group of order $n$, then the map $x \mapsto x^k$ is $d$-to-$1$, where $d=\gcd(k,n)$ because its kernel has order $d$. In other words, if $x^k=g$ has a solution, then it has $d$ ...
lhf's user avatar
  • 218k
4 votes
Accepted

Find a primitive element in the splitting field of $x^4-8x^2+15$.

Let $E$ be the splitting field of this polynomial $P(X) = X^4-8X^2+15$ over $\mathbb{Q}$. Since this is a biquadratic polynomial, it is easy to solve. In fact: $$P(X) = (X^2-3)(X^2-5)$$ So we see that ...
Jef's user avatar
  • 3,849
4 votes

$p^2$ misses 2 primitive roots

A small search with pari-gp shows that 367 is the smallest such prime, it misses the primitive roots 159 and 205. Then 653 misses four primitive roots 84,120,287 and 410. A search up to 20000 shows ...
Esteban Crespi's user avatar
4 votes
Accepted

Show that a certain set of elements is a basis of the free module $\mathbf{Z}[\xi]$

It is not sufficient to show that a set is linearly independent to show that it is an integral basis. For instance, consider $ \mathbf Z[\sqrt{2}] $ which is a free $ \mathbf Z $-module of rank $ 2 $ -...
Ege Erdil's user avatar
  • 17.8k
4 votes
Accepted

Assuming that $r$ is a primitive root of the odd prime $p$ prove that $ r^{(p-1)/2}\equiv -1 \pmod p $ holds

Note that we have that $r^{p-1} \equiv 1 \pmod p$ by Fermat's Little Theorem. Then we have that: $p \mid r^{p-1} - 1 = (r^{\frac{p-1}{2}} - 1)(r^{\frac{p-1}{2}} + 1)$. Now obviously $p$ must divide ...
Stefan4024's user avatar
  • 35.9k
4 votes

Irreducible polynomial, Primitive Polynomial and Minimal Polynomial

Start with $k = \mathbb{F}_p$ with $p$ prime. Then $k[x]$ is the ring of polynomials with coefficients in $k$, and $P(x) = \sum_{m=0}^n c_m x^m$ is irreducible means there is no polynomials $Q,R \in ...
reuns's user avatar
  • 78.4k
4 votes

How to prove $r^{\phi(m)/2} \equiv -1\pmod m$ if $r^{\phi(m)} \equiv 1\pmod m$?

If $r$ is a primitive root modulo $m$ then $1,r,r^2,\dots, r^{\phi(m)-1}$ are distinct modulo $m$. There are a couple of ways to proceed from this observation. For example: This means that $\mathbb ...
Thomas Andrews's user avatar
4 votes
Accepted

Galois theory question

Note that $43$ is prime. For any prime $p$ and $p$-th root of unity $\zeta$ we have $$\text{Gal}(\mathbb{Q}(\zeta)/\mathbb{Q}) \cong (\mathbb{Z}_p)* \cong \mathbb{Z}_{p-1},$$ the first isomorphism ...
M. Van's user avatar
  • 4,188
4 votes

Reluctant roots: $n$ is a primitive root of $p$ but not of $p^2$

If $g$ is a primitive root modulo $p$ (or even if it isn't), then $g^{p-1}\equiv1+kp\bmod{p^2}$ for some $k$, $0\le k\le p-1$. As Oscar Lanzi points out in the comments, $g$ is "reluctant" if and only ...
Gerry Myerson's user avatar
4 votes
Accepted

Prove that a primitive $q$-th root of unity is in the algebraic closure of $\Bbb F_p$

By definition $\omega$ is a root of $X^q-1\in\Bbb{F}_p[X]$, and by definition every polynomial in $\Bbb{F}_p[X]$ splits into linear factors in $\Omega[X]$. Hence $X-\omega\in\Omega[X]$ and so $\omega\...
Servaes's user avatar
  • 64k

Only top scored, non community-wiki answers of a minimum length are eligible