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 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 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} and every 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 \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 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 \sim} on 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} such 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 (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. 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 (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. 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)} 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 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\,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 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 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:

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 \bar{a} = \left[ a \right] = \left\{ b ~\mid~ a \sim b \right\}}

Now 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 = \left\{ \left[ \left( a, b \right) \right] ~\mid~ a,b \in D, b \ne 0 \right\}}

Lemma. 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 \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 \left[ \left( c,d \right) \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 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 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} .

Proof of multiplication. Choose two representatives 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) \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 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 (ac,bd)} equivalent to 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_1 d_1)} ?

We have from equivalence 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 a_1 b c_1 d = b_1 a d_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 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} .
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 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 \ne 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 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]} .

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