MATH 415 Lecture 17

« previous | Thursday, October 24, 2013 | next »

Euler's Theorem

Theorem 20.8. If $a$ is relatively prime to $n$, then $a^{\varphi (n)}-1$ is divisible by $n$. That is, $a^{\varphi (n)}\equiv 1(\mathrm{mod}n)$.

Note $\left|G_n\right|=\varphi (n)$

Solving Linear Congruences

Find all solutions of a linear congruence $ax\equiv b(\mathrm{mod}m)$, where $ax=b$ in ${\mathbb{\mathbb{Z}}}_m$.

Theorem 20.10

Let $m\in {\mathbb{\mathbb{Z}}}^{+}$ and $a\in {\mathbb{\mathbb{Z}}}_m$ be relatively prime to $m$.

For each $b\in {\mathbb{\mathbb{Z}}}_m$, the equation $ax=b$has a unique solution in ${\mathbb{\mathbb{Z}}}_m$.

Proof. By Theorem 20.6, a is a unit in

${\mathbb{\mathbb{Z}}}_m$

, so there exists a

$a^{-1}$

such that

$a^{-1}ax=x=a^{-1}b$

.

quod erat demonstrandum

Corollary. If $\mathrm{g}\mathrm{c}\mathrm{d}(a,m)=1$, then for any $b\in \mathbb{\mathbb{Z}}$ the congruence $ax=b(\mathrm{mod}m)$ has as solutions all integers in precisely one residue class modulo $m$.

This is precisely $s+m\mathbb{\mathbb{Z}}=\dots ,s-2m,s-m,s,s+m,s+2m,\dots ,s+km,\dots$.

Theorem 20.12

(generalization of previous theorem)

Let $m\in {\mathbb{\mathbb{Z}}}^{+}$, $a,b\in {\mathbb{\mathbb{Z}}}_m$, and $d=\mathrm{g}\mathrm{c}\mathrm{d}(a,m)$.

The equation $ax=b$ has a solution in ${\mathbb{\mathbb{Z}}}_m$ if and only if $d\mid b$. When $d\mid b$, the equation has exactly $d$ solutions.

Proof. In other words, when $d\nmid b$, then the equation has no solutions. Suppose $s\in {\mathbb{\mathbb{Z}}}_m$ is a solution, so $as\equiv b(\mathrm{mod}m)$. Then $as-b=qm$ for some $q\in \mathbb{\mathbb{Z}}$. Thus $b=as-qm$, which implies $m\mid a$ and $d\mid m$. Therefore $d\mid b$. Contradiction!

Now if $d\mid b$, then $a=a_{1}d$, $b=b_{1}d$, and $m_{1}d$ ($d$ divides everything). Then we have $as-b=qm$, so $a_{1}ds-b_{1}d=q{m}_{1}d$ and $a_{1}s=q{m}_1$. Therefore

$\begin{array}{r}as\equiv b(\mathrm{mod}m)\\ a_{1}s\equiv b_1{(\mathrm{mod}m)}_1\end{array}$

With $\mathrm{g}\mathrm{c}\mathrm{d}(a_1,b_1)=1$. Therefore the second form has a unique solution $\overline{s}\in {\mathbb{\mathbb{Z}}}_{m_1}$.

Now for ${\mathbb{\mathbb{Z}}}_m\to {\mathbb{\mathbb{Z}}}_{m_1}$, there are $d$ preimages $\{\overline{s}+k{m}_1\mid 0\le k<d,k\in {\mathbb{\mathbb{Z}}}^{+}\}$ in ${\mathbb{\mathbb{Z}}}_m$.

Corollary. The congruence $ax\equiv b(\mathrm{mod}m)$ has a solution if and only if $d\mid b$. When this is the case, the solutinos are exactly $d$ distinct residual classes modulo $m$.

From the previous example, we somehow arrive at

$\overline{s}+m\mathbb{\mathbb{Z}}$, $\overline{s}+m_1+m\mathbb{\mathbb{Z}}$, ..., $\overline{s}+(d-1)m_1+m\mathbb{\mathbb{Z}}$.

Example

Solve $12x\equiv 27(\mathrm{mod}18)$ for all $x\in \mathbb{\mathbb{Z}}$.

No solution because $\mathrm{g}\mathrm{c}\mathrm{d}(12,18)=6$, but $6\nmid 27$.

Solve $15x\equiv 27(\mathrm{mod}1)8$ for all $x\in \mathbb{\mathbb{Z}}$

$\mathrm{g}\mathrm{c}\mathrm{d}(15,18)=3$ and $3\mid 27$. Therefore solutions to this equation also satisfy $5x\equiv 9(\mathrm{mod}6)$ or equivalently $5x\equiv 3(\mathrm{mod}6)$

observe $5\cdot 5\equiv 1(\mathrm{mod}6)$, so $5^{-1}=5$. Therefore $x\equiv 3\cdot 5\equiv 3(\mathrm{mod}6)$ with series of solutions $3+18\mathbb{\mathbb{Z}}$, $3+6+18\mathbb{\mathbb{Z}}$, and $3+12+18\mathbb{\mathbb{Z}}$.

Quotient Fields

The integral domain $\mathbb{\mathbb{Z}}$ can be "embedded in" the field of rationals by definition $q\in \mathbb{\mathbb{Q}}⟹q=\frac{m}{n}$, where $m\in \mathbb{\mathbb{Z}}$ and $n\in \mathbb{\mathbb{N}}$.

In general, let $D$ be any integral domain. This can be "embedded" into a field $F$ (called a quotient field):

Let $a=\frac{m}{n}$, where $m,n\in D$. We put $a$ in $F$.

Constructing a Quotient Field

1. define what the elements of $F$ are
2. Define binary operations $+$ and $\cdot$
3. Check all field axioms
4. show that $D$ can be viewed as a subring of $F$ and every $x\in F$ can be presented as $\frac{a}{b}$ for $a,b\in D$

For example, $D\times D=\{(a,b)\mid a,b\in D\}$ is a subset of $S=D\times (D\setminus \left\{0\right\})$

We define an equivalence relation $\sim$ on $S$ such that $(a,b)\sim (c,d)$ if and only if $ad=bc$, or equivalently $\frac{a}{b}=\frac{c}{d}$:

1. reflexive. $(a,b)\sim (a,b)$ holds because of multiplicative commutivity in $D$ ($ab=ba$)
2. symmetric. $(a,b)\sim (c,d)$ implies $(c,d)\sim (a,b)$ holds by symmetry on equality.
3. transitivity. $(a,b)\sim (c,d)$ and Failed to parse (unknown function "\im"): {\displaystyle (c,d) \im (r,s)} gives $ad=bc$ and $cs=dr$. We write $asd=sad=sbc=bcs=bdr=brd$ Therefore $as=br$ by cancellation, giving $(a,b)\sim (r,s)$.

We form equivalence classes of $a$ as follows:

$\overline{a}=\left[a\right]=\{b\mid a\sim b\}$

Now $F=\{\left[(a,b)\right]\mid a,b\in D,b\ne 0\}$

Lemma. For $\left[(a,b)\right]$ and $\left[(c,d)\right]$ in $F$, the equations

$\begin{array}{rl}\left[(a,b)\right]+[(c,d)]& =\left[(ad+bc,bd)\right]\\ \left[(a,b)\right]\cdot [(c,d)]& =\left[(ac,bd)\right]\end{array}$

Give well-defined operations of addition and multiplication in $F$.

Proof of multiplication. Choose two representatives $(a_1,b_1)\in \left[(a,b)\right]$ and $(c_1,d_1)\in \left[(c,d)\right]$. Then $(a_1,b_1)\sim (a,b)⟺a{b}_1=b{a}_1$ and $(c_1,d_1\sim (c,d)⟺c{d}_1=d{c}_1$.

Take product:

$\begin{array}{rl}(a_1,b_1)\cdot (c_1,d_1)& =(a_1{c}_1,b_1{d}_1)\\ (a,b)\cdot (c,d)& =(ac,bd)\end{array}$

The question is: is $(ac,bd)$ equivalent to $(a_1{c}_1,b_1{d}_1)$?

We have from equivalence definition

$a_{1}b{c}_{1}d=b_{1}a{d}_{1}c$

, so by commutativity,

$a_1{c}_{1}bd=b_1{d}_{1}ac$

; so yes.

quod erat demonstrandum

Checking Field Axioms

1. Addition is commutative
2. Addition is associative
3. Addition has identity $\left[(0,1)\right]=0_F$
4. Additive inverse is defined as $-\left[(a,b)\right]=\left[(-a,b)\right]$
5. Multiplication is commutative
6. Multiplication is associative
7. Multiplication has identity $\left[(1,1)\right]=1_F$
8. Distributive laws hold in $F$.
9. If $\left[(a,b)\right]\in F$ is not the additive identity $0_F$, then $a\ne 0$ in $D$ and $\left[(b,a)\right]$ is a multiplicative inverse for $\left[(a,b)\right]$.

To review,

• (1-4) shows that $⟨F,+⟩$ is an abelian group
• 5 shows that $⟨F,\cdot ⟩$ is a semigroup
• 6 shows that $⟨F,\cdot ⟩$ is commutative