NoteNextra-origin/content/Math4302/Math4302_L26.md

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.

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.

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 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.