14 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.2k
8 votes
Accepted

How to prove 2 is a primitive root mod 37, without calculating all powers of 2 mod 37?

The order of any element in an order 36 group is a factor of 36 (Lagrange's theorem), so it suffices to check $2^a \not\equiv 1\pmod{37}$ for $a \in \{1, 2, 3, 4, 6, 9, 12, 18\}$. But in fact that ...
  • 13.1k
8 votes

Solve $x^8 \equiv 3 \pmod {13}$

In $\mathbb{F}_{13}$, $$ x^8-3 = x^8-16 = (x^4-4)(x^4+4)=(x^2-2)(x^2+2)(x^2+2x+2)(x^2-2x+2) $$ hence we just have to check which of the numbers $-2,2,-1$ are quadratic residues. Since $13$ is a prime ...
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.
  • 38.4k
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+...
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.2k
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 ...
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 ...
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 ...
  • 26.3k
7 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 ...
  • 2,619
6 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 ...
  • 65.7k
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$ (...
  • 38.6k
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$
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,759
6 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 ...
  • 63.1k
5 votes

Primitive roots modulo n

First, existence: there is a primitive root modulo $n$ if and only if $n$ is $1$ or $2$ or $4$ or $p^\alpha$ or $2p^\alpha$, where $p$ is prime, $p\ne2$, and $\alpha\ge1$. Second, a systematic way of ...
  • 78.1k
5 votes

$g^q-q$ and $g^q-gq$ are primitive roots modulo $q^2$

Let $a=g^p-cp$ with $c\not\equiv 0\pmod p$. First observe that $g^p-cp\equiv g\pmod p$ by Fermat. Since the order of $g$ modulo $p$ is $p-1$, the order of $a$ modulo $p^2$ is certainly a multiple of $...
5 votes
Accepted

Solve $x^8 \equiv 3 \pmod {13}$

No, your answer is correct, $t = 2,5,8,11$ give respectively $x = 4,6,9,7$. For the sake of Google, I will write out the method OP probably used, which is different from the one used in the other ...
  • 3,109
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 ...
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$. ...
  • 87.2k
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\...
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?$$
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\...
4 votes

About primitive roots and square free numbers.

Checking per Gerry's suggestion, a quick spreadsheet for the 40 primitive roots mod 101 shows that twenty-six (26) of them are square-free and fourteen (14) of them are not. We are helped in this by ...
4 votes

Proving a number has no primitive roots

There is a known result about this. It's not especially easy to prove. Theorem. An integer $n\ge2$ has a primitive root if and only if it is one of the following: $2$, $4$, $p^\alpha$, $2p^\alpha$, ...
  • 78.1k
4 votes

primitive roots problem. that integer n can never have exactly 26 primitive roots.

$\phi(m)=26$ is impossible. We have for prime $p$, $\phi(p^a)=p^a-p^{a-1}=(p-1)\cdot p^{a-1}$. Also $\phi$ is multiplicative (that is, for $\gcd(j,k)=1$, $\phi(jk)=\phi(j)\phi(k)$). From these ...
  • 38.4k
4 votes
Accepted

Proof of primitive roots in $F_{128}$

Note that $\Bbb F_{128}^\times$ is a group with 127 elements. Since 127 is prime, every one of the 126 non-trivial elements generates the whole group.
  • 12.1k

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