15
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^...
- 16.5k
8
votes
Solve $ x^2 = 2$ over $ F_5 $.
Since $F_5$ is a field with only five elements, it is perhaps simplest to solve the equation by just trying each element.
- 39.7k
8
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 ...
- 3,143
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 ...
- 19.6k
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+...
- 502k
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 \...
- 17.6k
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 ...
- 14.3k
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 ...
- 73.6k
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 ...
- 61.4k
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 ...
- 28k
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$ (...
- 39.4k
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$
- 86.7k
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$$
- 1,765
5
votes
Show that 7 is a primitive root modulo 601
Because $601$ is a prime, the group $\Bbb{Z}_{601}^*$ has order $600$. By Lagrange, the order $e$ of $7$ in this group is a factor of $600=2^3\cdot3\cdot5^2$.
You want to prove that $e=600$, which ...
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 ...
- 67.9k
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$.
...
- 89.8k
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\...
- 351k
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?$$
- 272k
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\...
- 130k
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 ...
- 67k
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 ...
- 106
4
votes
Accepted
Find all incongruent solutions of $x^8\equiv3\pmod{13}$.
$$x^8-3\equiv x^8-16\equiv \left(x^2-2\right)\left(x^2+2\right)\left(x^4+4\right)\pmod{13}$$
$x^2\equiv 2\pmod{13}$ and $x^2\equiv -2\pmod{13}$ are both unsolvable (by Quadratic Reciprocity), because ...
- 13.2k
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 ...
- 3,801
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$ ...
- 214k
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 ...
- 3,957
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 $ -...
- 17.6k
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 ...
- 35.6k
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 ...
- 76.9k
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 ...
- 175k
Only top scored, non community-wiki answers of a minimum length are eligible