NoteNextra-origin/content/Math4302/Math4302_L27.md

Math4302 Modern Algebra (Lecture 27)

Rings

Fermat’s and Euler’s Theorems

Recall from last lecture, ax\equiv b \mod n, if x\equiv y\mod n, then x is a solution if and only if y is a solution.

Theorem for existence of solution of modular equations

ax\equiv b\mod n has a solution if and only if d=\operatorname{gcd}(a,n)|b And if there is a solution, then there are exactly d solutions in \mathbb{Z}_n.

Proof

For the forward direction, we proved if ax\equiv b\mod n then ax-b=ny, y\in\mathbb{Z}.

then b=ax-ny, d|(ax-ny) implies that d|b.

---

For the backward direction, assume d=\operatorname{gcd}(a,n)=1. Then we need to show, there is exactly 1 solution between 0 and n-1.

If ax\equiv b\mod n, then in \mathbb{Z}_n, [a][x]=[b]. (where [a] denotes the remainder of a by n and [b] denotes the remainder of b by n)

Since \operatorname{gcd}(a,n)=1, then [a] is a unit in \mathbb{Z}_n, so we can multiply the above equation by the inverse of [a]. and get [x]=[a]^{-1}[b].

Now assume d=\operatorname{gcd}(a,n) where n is arbitrary. Then a=a'd, then n=n'd, with \operatorname{gcd}(a',n')=1.

Also d|b so b=b'd. So

\begin{aligned}
ax\equiv b \mod n&\iff n|(ax-b)\\
&\iff n'd|(a'dx-b'd)\\
&\iff n'|(a'x-b')\\
&\iff a'x\equiv b'\mod n'
\end{aligned}
$$.

Since $\operatorname{gcd}(a',n')=1$, there is a unique solution $x_0\in \mathbb{Z}_{n'}$. $0\leq x_0\leq n'+1$. Other solution in $\mathbb{Z}$ are of the form $x_0+kn'$ for $k\in \mathbb{Z}$.

And there will be $d$ solutions in $\mathbb{Z}_n$,

</details>

<details>
<summary>Examples</summary>

Solve $12x\equiv 25\mod 7$.

$12\equiv 5\mod 7$, $25\equiv 4\mod 7$. So the equation becomes $5x\equiv 4\mod 7$.

$[5]^{-1}=3\in \mathbb{Z}_7$, so $[5][x]\equiv [4]$ implies $[x]\equiv [3][4]\equiv [5]\mod 7$.

So solution in $\mathbb{Z}$ is $\{5+7k:k\in \mathbb{Z}\}$.

---

Solve $6x\equiv 32\mod 20$.

$\operatorname{gcd}(6,20)=2$, so $6x\equiv 12\mod 20$ if and only if $3x\equiv 6\mod 10$.

$[3]^{-1}=[7]\in \mathbb{Z}_{10}$, so $[3][x]\equiv [6]$ implies $[x]\equiv [7][6]\equiv [2]\mod 10$.

So solution in $\mathbb{Z}_{20}$ is $[2]$ and $[12]$

So solution in $\mathbb{Z}$ is $\{2+10k:k\in \mathbb{Z}\}$

</details>

### Ring homomorphisms

#### Definition of ring homomorphism

Let $R,S$ be two rings, $f:R\to S$ is a ring homomorphism if $\forall a,b\in R$,

- $f(a+b)=f(a)+f(b)\implies f(0)=0, f(-a)=-f(a)$
- $f(ab)=f(a)f(b)$

#### Definition of ring isomorphism

If $f$ is a ring homomorphism and a bijection, then $f$ is called a ring isomorphism.

<details>
<summary>Example</summary>
Let $f:(\mathbb{Z},+,\times)\to(2\mathbb{Z},+,\times)$ by $f(a)=2a$.

Is not a ring homomorphism since $f(ab)\neq f(a)f(b)$ in general.

---

Let $f:(\mathbb{Z},+,\times)\to(\mathbb{Z}_n,+,\times)$ by $f(a)=a\mod n$

Is a ring homomorphism.

</details>

### Integral domains and their file fo fractions.

Let $R$ be an integral domain: (i.e. $R$ is commutative with unity and no zero divisors).

#### Definition of field of fractions

If $R$ is an integral domain, we can construct a field containing $R$ called the field of fractions (or called field of quotients) of $R$.

S={(a,b)|a,b\in R, b\neq 0}

a relation on $S$ is defined as follows:

$(a,b)\sim (c,d)$ if and only if $ad=bc$.

<details>
<summary>This equivalence relation is well defined</summary>

- Reflectivity: $(a,b)\sim (a,b)$ $ab=ab$
- Symmetry: $(a,b)\sim (c,d)\Rightarrow (c,d)\sim (a,b)$
- Transitivity: $(a,b)\sim (c,d)$ and $(c,d)\sim (e,f)\Rightarrow (a,b)\sim (e,f)$
  - $ad=bc$, and $cf=ed$, we want to conclude that $af=be$. since $ad=bc$, then $adf=bcf$, since $cf=ed$, then $cfb=edb$, therefore $adf=edb$.
  - Then $d(af-be)=0$ since $d\neq 0$ then $af=be$.

</details>

Then $S/\sim$ is a field.