87a5182ac6
Some checks failed
Sync from Gitea (main→main, keep workflow) / mirror (push) Has been cancelled
111 lines
3.0 KiB
Markdown
111 lines
3.0 KiB
Markdown
# 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$.
|
||
|
||
So
|
||
|
||
#### 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$.
|
||
|
||
<details>
|
||
<summary>Proof</summary>
|
||
|
||
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$.
|
||
|
||
</details>
|
||
|
||
<details>
|
||
<summary>Example</summary>
|
||
|
||
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)$.
|
||
|
||
</details>
|
||
|
||
#### 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\}|
|
||
$$
|
||
|
||
<details>
|
||
<summary>Example</summary>
|
||
|
||
$\phi(8)=|\{1,3,5,7\}|=4$
|
||
|
||
</details>
|
||
|
||
If $[a]\in \mathbb{Z}_n^*$, then $[a]^{\phi(n)}=[1]$. So $a^{\phi(n)}\equiv 1\mod n$.
|
||
|
||
#### Theorem
|
||
|
||
If $m\in \mathbb{Z}$, and $gcd(m,n)=1$, then $m^{\phi(n)}\equiv 1\mod n$.
|
||
|
||
<details>
|
||
<summary>Proof</summary>
|
||
|
||
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$.
|
||
|
||
</details>
|
||
|
||
#### 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 exsistence 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. |