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 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 6 \nmid 27} .

Solve 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 15x \equiv 27 \pmod 18} for all 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 \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 \mathrm{gcd}\left(15, 18\right)=3} 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 \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 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^{-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 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 + 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 $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 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