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 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 \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 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 5x \equiv 9 \pmod 6} or equivalently 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 5x \equiv 3 \pmod 6}

observe 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 5 \cdot 5 \equiv 1 \pmod 6} , so $5^{-1}=5$. Therefore 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 x \equiv 3 \cdot 5 \equiv 3 \pmod{6}} with series of solutions $3+18\mathbb {Z}$, 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 3 + 6 + 18 \mathbb{Z}} , 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 3 + 12 + 18 \mathbb{Z}} .

Quotient Fields

The integral domain $\mathbb {Z}$ can be "embedded in" the field of rationals by definition 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 q \in \mathbb{Q} \implies q = \frac{m}{n}} , where $m\in \mathbb {Z}$ 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 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 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 a = \frac{m}{n}} , where 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 m,n\in D} . We put $a$ in 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 F} .

Constructing a Quotient Field

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

For example, 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 D \times D = \left\{ (a,b) ~\mid~ a,b \in D \right\}} is a subset of 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 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 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 a\,d = b \, c} , or equivalently 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 \frac{a}{b} = \frac{c}{d}} :

1. reflexive. $(a,b)\sim (a,b)$ holds because of multiplicative commutivity in 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 D} (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 a\,b = b\,a} )
2. symmetric. 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 (a,b) \sim (c,d)} implies 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) \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 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 a\,d = b\,c} and $c\,s=d\,r$. We write 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 asd = sad = sbc = bcs = bdr = brd} Therefore $as=br$ by cancellation, giving 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 (a,b) \sim (r,s)} .

We form equivalence classes of 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 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

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 \begin{align} \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{align}}

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 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_1,d_1) \in \left[ \left( c,d \right) \right]} . Then 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 (a_1, b_1) \sim (a,b) \iff a \, b_1 = b \, a_1} 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_1,d_1 \sim (c,d) \iff c \, d_1 = d \, c_1} .

Take product:

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 \begin{align} (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{align}}

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, 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 a_1 c_1 b d = b_1 d_1 a c} ; so yes.

quod erat demonstrandum

Checking Field Axioms

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

To review,

• (1-4) shows that 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 \left\langle F, + \right\rangle} is an abelian group
• 5 shows that 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 \left\langle F, \cdot \right\rangle} is a semigroup
• 6 shows that 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 \left\langle F, \cdot \right\rangle} is commutative