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^{\phi (n)}-1$ is divisible by $n$. That is, $a^{\phi (n)}\equiv 1{\pmod {n}}$.

Note $\left|G_{n}\right|=\phi (n)$

Solving Linear Congruences

Find all solutions of a linear congruence $a\,x\equiv b{\pmod {m}}$, where $a\,x=b$ in $\mathbb {Z} _{m}$.

Theorem 20.10

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

For each $b\in \mathbb {Z} _{m}$, the equation $a\,x=b$has a unique solution in $\mathbb {Z} _{m}$.

Proof. By Theorem 20.6, a is a unit in $\mathbb {Z} _{m}$, so there exists a $a^{-1}$ such that $a^{-1}\,a\,x=x=a^{-1}\,b$.

quod erat demonstrandum

Corollary. If $\mathrm {gcd} \left(a,m\right)=1$, then for any $b\in \mathbb {Z}$ the congruence $a\,x=b{\pmod {m}}$ has as solutions all integers in precisely one residue class modulo $m$.

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

Theorem 20.12

(generalization of previous theorem)

Let $m\in \mathbb {Z} ^{+}$, $a,b\in \mathbb {Z} _{m}$, and $d=\mathrm {gcd} \left(a,m\right)$.

The equation $a\,x=b$ has a solution in $\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 {Z} _{m}$ is a solution, so $a\,s\equiv b{\pmod {m}}$. Then $a\,s-b=q\,m$ for some $q\in \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 $a\,s-b=q\,m$, so $a_{1}\,d\,s-b_{1}\,d=q\,m_{1}\,d$ and $a_{1}\,s=q\,m_{1}$. Therefore

${\begin{aligned}a\,s\equiv b{\pmod {m}}\\a_{1}\,s\equiv b_{1}{\pmod {m}}_{1}\end{aligned}}$

With $\mathrm {gcd} \left(a_{1},b_{1}\right)=1$. Therefore the second form has a unique solution ${\bar {s}}\in \mathbb {Z} _{m_{1}}$.

Now for $\mathbb {Z} _{m}\to \mathbb {Z} _{m_{1}}$, there are $d$ preimages $\left\{{\bar {s}}+k\,m_{1}~\mid ~0\leq k<d,k\in \mathbb {Z} ^{+}\right\}$ in $\mathbb {Z} _{m}$.

Corollary. The congruence $a\,x\equiv b{\pmod {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

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

Example

Solve $12x\equiv 27{\pmod {18}}$ for all $x\in \mathbb {Z}$.

No solution because $\mathrm {gcd} \left(12,18\right)=6$, but $6\nmid 27$.

Solve $15x\equiv 27{\pmod {1}}8$ for all $x\in \mathbb {Z}$

$\mathrm {gcd} \left(15,18\right)=3$ and $3\mid 27$. Therefore solutions to this equation also satisfy $5x\equiv 9{\pmod {6}}$ or equivalently $5x\equiv 3{\pmod {6}}$

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

Quotient Fields

The integral domain $\mathbb {Z}$ can be "embedded in" the field of rationals by definition $q\in \mathbb {Q} \implies q={\frac {m}{n}}$, where $m\in \mathbb {Z}$ and $n\in \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=\left\{(a,b)~\mid ~a,b\in D\right\}$ is a subset of $S=D\times \left(D\setminus \left\{0\right\}\right)$

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

1. reflexive. $(a,b)\sim (a,b)$ holds because of multiplicative commutivity in $D$ ($a\,b=b\,a$)
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 (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (c,d) \im (r,s)} gives $a\,d=b\,c$ and $c\,s=d\,r$. 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:

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

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

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

${\begin{aligned}\left[\left(a,b\right)\right]+\left[(c,d)\right]&=\left[\left(a\,d+b\,c,b\,d\right)\right]\\\left[\left(a,b\right)\right]\cdot \left[(c,d)\right]&=\left[\left(a\,c,b\,d\right)\right]\end{aligned}}$

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

Proof of multiplication. Choose two representatives $(a_{1},b_{1})\in \left[\left(a,b\right)\right]$ and $(c_{1},d_{1})\in \left[\left(c,d\right)\right]$. Then $(a_{1},b_{1})\sim (a,b)\iff a\,b_{1}=b\,a_{1}$ and $(c_{1},d_{1}\sim (c,d)\iff c\,d_{1}=d\,c_{1}$.

Take product:

${\begin{aligned}(a_{1},b_{1})\cdot (c_{1},d_{1})&=(a_{1}\,c_{1},b_{1}\,d_{1})\\(a,b)\cdot (c,d)&=(a\,c,b\,d)\end{aligned}}$

The question is: is $(ac,bd)$ equivalent to $(a_{1}c_{1},b_{1}d_{1})$?

We have from equivalence definition $a_{1}bc_{1}d=b_{1}ad_{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[\left(0,1\right)\right]=0_{F}$
4. Additive inverse is defined as $-\left[\left(a,b\right)\right]=\left[\left(-a,b\right)\right]$
5. Multiplication is commutative
6. Multiplication is associative
7. Multiplication has identity $\left[\left(1,1\right)\right]=1_{F}$
8. Distributive laws hold in $F$.
9. If $\left[\left(a,b\right)\right]\in F$ is not the additive identity $0_{F}$, then $a\neq 0$ in $D$ and $\left[\left(b,a\right)\right]$ is a multiplicative inverse for $\left[\left(a,b\right)\right]$.

To review,

• (1-4) shows that $\left\langle F,+\right\rangle$ is an abelian group
• 5 shows that $\left\langle F,\cdot \right\rangle$ is a semigroup
• 6 shows that $\left\langle F,\cdot \right\rangle$ is commutative