Math4302 Modern Algebra (Lecture 26)

Rings

Fermat’s and Euler’s Theorems

Recall from last lecture, we consider $\mathbb{Z}_p$ and $\mathbb{Z}_p^*$ denote the group of units in $\mathbb{Z}_p$ with multiplication.

\mathbb{Z}_p^* = \{1,2,\cdots,p-1\}, \quad |\mathbb{Z}_p^*| = p-1

Let $[a]\in \mathbb{Z}_p^*$ , then $[a]^{p-1}=[1]$ , this implies that $a^{p-1}\mod p=1$ .

Now if $m\in \mathbb{Z}$ and $a=$ remainder of $m$ by $p$ , $[a]\in \mathbb{Z}_p$ , implies $m\equiv a\mod p$ .

Then $m^{p-1}\equiv a^{p-1}\mod p$ .

Fermat’s little theorem

If $p$ is not a divisor of $m$ , then $m^{p-1}\equiv 1\mod p$ .

Corollary of Fermat’s little theorem

If $m\in \mathbb{Z}$ , then $m^p\equiv m\mod p$ .

Proof

If $p|m$ , then $m^{p-1}\equiv 0\equiv m\mod p$ .

If $p\not|m$ , then by Fermat’s little theorem, $m^{p-1}\equiv 1\equiv m\mod p$ , so $m^p\equiv m\mod p$ .

Example

Find the remainder of $40^{100}$ by $19$ .

$40^{100}\equiv 2^{100}\mod 19$

$2^{100}\equiv 2^{10}\mod 19$ (Fermat’s little theorem $2^18\equiv 1\mod 19, 2^{90}\equiv 1\mod 19$ )

$2^10\equiv (-6)^2\mod 19\equiv 36\mod 19\equiv 17\mod 19$

For every integer $n$ , $15|(n^{33}-n)$ .

$15=3\cdot 5$ , therefore enough to show that $3|(n^{33}-n)$ and $5|(n^{33}-n)$ .

Apply the corollary of Fermat’s little theorem to $p=3$ : $n^3\equiv n\mod 3$ , $(n^3)^11\equiv n^{11}\equiv (n^3)^3 n^2=n^3 n^2\equiv n^3\mod 3\equiv n\mod 3$ .

Therefore $3|(n^{33}-n)$ .

Apply the corollary of Fermat’s little theorem to $p=5$ : $n^5\equiv n\mod 5$ , $n^30 n^3\equiv (n^5)^6 n^3\equiv n^6 n^3\equiv n^5\mod 5\equiv n\mod 5$ .

Therefore $5|(n^{33}-n)$ .

Euler’s totient function

Consider $\mathbb{Z}_6$ , by definition for the group of units, $\mathbb{Z}_6^*=\{1,5\}$ .

\phi(n)=|\mathbb{Z}_n^*|=|\{1\leq x\leq n:gcd(x,n)=1\}|

Example

$\phi(8)=|\{1,3,5,7\}|=4$

If $[a]\in \mathbb{Z}_n^*$ , then $[a]^{\phi(n)}=[1]$ . So $a^{\phi(n)}\equiv 1\mod n$ .

Euler’s Theorem

If $m\in \mathbb{Z}$ , and $gcd(m,n)=1$ , then $m^{\phi(n)}\equiv 1\mod n$ .

Proof

If $a$ is the remainder of $m$ by $n$ , then $m\equiv a\mod n$ , and $\operatorname{gcd}(a,n)=1$ , so $m^{\phi(n)}\equiv a^{\phi(n)}\equiv 1\mod n$ .

Applications on solving modular equations

Solving equations of the form $ax\equiv b\mod n$ .

Not always have solution, $2x\equiv 1\mod 4$ has no solution since $1$ is odd.

Solution for $2x\equiv 1\mod 3$

$x\equiv 0\implies 2x\equiv 0\mod 3$
$x\equiv 1\implies 2x\equiv 2\mod 3$
$x\equiv 2\implies 2x\equiv 1\mod 3$

So solution for $2x\equiv 1\mod 3$ is $\{3k+2|k\in \mathbb{Z}\}$ .

Theorem for existence of solution of modular equations

$ax\equiv b\mod n$ has a solution if and only if $\operatorname{gcd}(a,n)|b$ and in that case the equation has $d$ solutions in $\mathbb{Z}_n$ .

Proof on next lecture.