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

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

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

It's enough to consider $g=1$

To conclude, $ax\equiv b{\pmod {n}}\iff a\,x+n\,y=b$ has only one solution.

Now suppose if there are two solutions $(x_{1},y_{1})$ and $(x_{2},y_{2})$, then we get

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

$\mathrm {GCD} (a,n)=1$, so since $n$ divides the RHS, it also divides the LHS

Therefore, $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)

${\begin{cases}2x+3y=1&{\pmod {26}}\\7x+14y=2&{\pmod {26}}\end{cases}}$

Put into an augmented matrix

${\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

${\begin{bmatrix}2&3&1\\7&14&2\end{bmatrix}}\rightarrow {\begin{bmatrix}1&5&-1\\0&-7&3\end{bmatrix}}$

${\begin{aligned}x+5y&=-1{\pmod {26}}\\-7y&=3{\pmod {26}}\end{aligned}}$

We can invert -1/7 mod 26:

$-{\frac {1}{7}}=-15=11{\pmod {26}}$

${\begin{aligned}y&=3\cdot 11=7{\pmod {26}}\\x&=-36=16{\pmod {26}}\end{aligned}}$

Second Option

Cramer's rule

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