MATH 470 Lecture 2

« previous | Thursday, January 17, 2013 | next »

Fundamental Theorem of Arithmatic

Any $n\in \mathbb {Z}$ can be written as $n=\prod _{i=1}^{k}p_{i}^{a_{i}}$ for pairwise distinct primes $p_{1},\ldots ,p_{k}$ and $a_{1},\ldots ,a_{k}\in \mathbb {Z}$

Corollary

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}(p_1^{a_1} \dots p_k^{a_k}, p_1^{b_1} \dots p_1^{\min{(a_1,b_1)}} \dots p_k^{\min{(a_k,b_k)}}}

Corollary

If $a,x,n\in \mathbb {Z}$ with $\mathrm {GCD} (a,n)$ = 1 and $n\mid (a\,x),then<math>n\mid x$

Extended Euclidean Algorithm

Input: $a,b\in \mathrm {Z}$
Output: $g:=\mathrm {GCD} (a,b)$ and $(x,y)\in \mathbb {Z} ^{2}$ with $a\,x+b\,y=g$

1. Form matrix ${\begin{bmatrix}1&0\\0&1\\a&b\end{bmatrix}}$
2. Use elementary column operations (only allowing divisions by ≠ 1) to reduce to ${\begin{bmatrix}u&x\\v&y\\0&g\end{bmatrix}}$
3. You have your answers $g$, $x$, and $y$

Example

Solve $173x=3{\pmod {256}}$

Rewrite as $173x+256y=3$. Find $x$ and $y$ such that $173x+256y=1$

${\begin{aligned}{\begin{bmatrix}1&0\\0&1\\173&256\end{bmatrix}}\longrightarrow {\begin{bmatrix}1&-1\\0&1\\173&83\end{bmatrix}}\rightarrow {\begin{bmatrix}3&-1\\-2&1\\7&83\end{bmatrix}}\rightarrow {\begin{bmatrix}3&-34\\-2&23\\7&6\end{bmatrix}}\rightarrow {\begin{bmatrix}37&-34\\-25&23\\1&6\end{bmatrix}}\rightarrow {\begin{bmatrix}37&-256\\-25&173\\1&0\end{bmatrix}}\rightarrow {\begin{bmatrix}-256&37\\173&-25\\0&1\end{bmatrix}}\end{aligned}}$

Therefore, all of the following are true:

• $173(37)+256(-25)=1$
• $173\cdot 37=1{\pmod {256}}$
• ${\frac {1}{173}}=37{\pmod {256}}$

${\begin{aligned}{\frac {1}{173}}173x&=3\left({\frac {1}{173}}\right){\pmod {256}}\\&=3\cdot 37{\pmod {256}}\\&=111{\pmod {256}}\end{aligned}}$

Complexity: Lame's Theorem

Number of column operations needed is ≤ 5 × number of digits in smaller number

Theorem on Congruences

Given any $\color {Yellow}a,b,n\in \mathbb {Z}$, the congruence $\color {Yellow}ax{=}b{\pmod {n}}$ has exactly $\color {Yellow}g:{=}\mathrm {GCD} (a,n)$ solutions when $\color {Yellow}g\mid b$ and no solutions otherwise

Example

$27x=18{\pmod {45}}$ has solutions $\{4,9,14,19,24,29,34,39,44\}$.

How would we have known?

1. find $\mathrm {GCD} (a,n)$ via Extended Euclidean Algorithm ($\mathrm {GCD} (27,45)=9$; $27(2)+45(-1)=9$)
2. divide out equation by $g$ ($3x=2{\pmod {5}}$)
3. solve equation above ($x=4$)
4. solutions are: $\left\{x,x+{\frac {n}{g}},\ldots ,x+(g-1)\,{\frac {n}{g}}\right\}$

Proof

First note that $g\nmid b$ implies no solutions.

Indeed $ax=b{\pmod {n}}$ implies $ax+ny=b$ for some $x,y\in \mathbb {Z}$.

$g\mid (ax+ny)$, so $g\nmid b$ leads to a contradiction.

For example, $2x=1{\pmod {8}}$ cannot be solved since $2x+8y$ is even and $1$ is odd.

Let's assume $g\mid b$

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 g \mid \{a,b,n\}} , 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 x} is any solution 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 ax = b \pmod{n}} , so 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 x + i\left(\frac{n}{g}\right)} for any 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 i \in \{0,\ldots,g-1 \}}

Indeed, 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 \left(x+i\left(\frac{n}{g} \right)\right) \equiv ax + i \left(\frac{a\,n}{g} \right) \equiv b + i\,n \left( \frac{a}{g} \right) \equiv b \pmod{n}}

Moreover, 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{n}{g}, \frac{2n}{g}, \ldots, \frac{(g-1)n}{g}} are clearly distinct mod 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}

It's enough to consider 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 g = 1}

To conclude, 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 ax \equiv b \pmod{n} \iff a\,x + n\,y = b} has only one solution.

Now suppose if there are two 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 (x_1,y_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 (x_2,y_2)} , then we get

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\,x_1 + n \, y_1 &= b \\ a\,x_2 + n \, y_2 &= b \\ a(x_1 - x_2) + n(y_1 - y_2) = 0 \end{align}}

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}(a,n) = 1} , so since 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} divides the RHS, it also divides the LHS

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 n \mid (x_1-x_2) \implies x_1 \equiv x_2 \pmod{n}}

Q.E.D.

CAS Stuff

Maple

> (* Matrices *)
> M := matrix([[a,b,c],[d,e,f],[g,h,i]]);

Sage

sage: # Affine Ciphers == of the form: f(x) = a*x + b (mod 26)
sage: A = AffineCryptosystem(AlphabeticStrings());
sage: P = A.encoding("Hey! How's it going?");
  => HEYHOWSITGOING
sage: a,b = (9,13);
sage: cipher = A.enciphering(a,b,P);
  => YXVYJDTHCPJHAP

Solving Linear Systems

(mod an integer)

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{cases} 2x + 3y = 1 & \pmod{26} \\ 7x + 14y = 2 & \pmod{26} \end{cases}}

Put into an augmented matrix

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{bmatrix} 2 & 3 & 1 \\ 7 & 14 & 2 \end{bmatrix}}

First operation would be to subtract 7/2 times the first row from the second row... TROUBLE! What's 1/2 mod 26? (undefined)

2 options

1. Do gaussian elimination without dividing by two (similar to E.E.A.)
2. Use adjoints

First Option

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{bmatrix} 2 & 3 & 1 \\ 7 & 14 & 2 \end{bmatrix} \rightarrow \begin{bmatrix} 1 & 5 & -1 \\ 0 & -7 & 3 \end{bmatrix}}

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} x + 5y &= -1 \pmod{26} \\ -7y &= 3 \pmod{26} \end{align}}

We can invert -1/7 mod 26:

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{1}{7} = -15 = 11 \pmod{26}}

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} y &= 3 \cdot 11 = 7 \pmod{26} \\ x &= -36 = 16 \pmod{26} \end{align}}

Second Option

Cramer's rule

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,y) = \left( \frac{\begin{vmatrix}1&3\\2&14\end{vmatrix}}{\begin{vmatrix}2&3\\7&14\end{vmatrix}}, \frac{\begin{vmatrix}2&1\\7&2\end{vmatrix}}{\begin{vmatrix}2&3\\7&14\end{vmatrix}} \right)}

We only have to invert 7, which is relatively prime to 26, so it is possible.

Theorem

You can 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 Ax = b \pmod{n}} for any $k\times k$ matrix of integers 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} and any 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 k \times 1} vector of integers 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 b} when 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(\left|A\right|,n \right) = 1}