MATH 470 Lecture 2

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

Fundamental Theorem of Arithmatic

Any $n\in \mathbb{\mathbb{Z}}$ can be written as $n=\prod _{i=1}^k{p}_i^{a_i}$ for pairwise distinct primes $p_1,\dots ,p_k$ and $a_1,\dots ,a_k\in \mathbb{\mathbb{Z}}$

Corollary

$\mathrm{G}\mathrm{C}\mathrm{D}(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{\mathbb{Z}}$ with $\mathrm{G}\mathrm{C}\mathrm{D}(a,n)$ = 1 and $n\mid (ax),then<math>n\mid x$

Extended Euclidean Algorithm

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

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

Example

Solve $173x=3(\mathrm{mod}256)$

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

$\begin{array}{r}\left[\begin{array}{cc}1& 0\\ 0& 1\\ 173& 256\end{array}\right]⟶\left[\begin{array}{cc}1& -1\\ 0& 1\\ 173& 83\end{array}\right]\to \left[\begin{array}{cc}3& -1\\ -2& 1\\ 7& 83\end{array}\right]\to \left[\begin{array}{cc}3& -34\\ -2& 23\\ 7& 6\end{array}\right]\to \left[\begin{array}{cc}37& -34\\ -25& 23\\ 1& 6\end{array}\right]\to \left[\begin{array}{cc}37& -256\\ -25& 173\\ 1& 0\end{array}\right]\to \left[\begin{array}{cc}-256& 37\\ 173& -25\\ 0& 1\end{array}\right]\end{array}$

Therefore, all of the following are true:

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

$\begin{array}{rl}\frac{1}{173}173x& =3\left(\frac{1}{173}\right)(\mathrm{mod}256)\\ & =3\cdot 37(\mathrm{mod}256)\\ & =111(\mathrm{mod}256)\end{array}$

Complexity: Lame's Theorem

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

Theorem on Congruences

Given any $a,b,n\in \mathbb{\mathbb{Z}}$, the congruence $ax=b(\mathrm{mod}n)$ has exactly $g:=\mathrm{G}\mathrm{C}\mathrm{D}(a,n)$ solutions when $g\mid b$ and no solutions otherwise

Example

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

How would we have known?

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

Proof

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

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

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

For example, $2x=1(\mathrm{mod}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(\mathrm{mod}n)$, so is $x+i\left(\frac{n}{g}\right)$ for any $i\in \{0,\dots ,g-1\}$

Indeed, $a(x+i\left(\frac{n}{g}\right))\equiv ax+i\left(\frac{an}{g}\right)\equiv b+in\left(\frac{a}{g}\right)\equiv b(\mathrm{mod}n)$

Moreover, $\frac{n}{g},\frac{2n}{g},\dots ,\frac{(g-1)n}{g}$ are clearly distinct mod $n$

It's enough to consider $g=1$

To conclude, $ax\equiv b(\mathrm{mod}n)⟺ax+ny=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{array}{rl}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{array}$

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

Therefore, $n\mid (x_1-x_2)⟹x_1\equiv x_2(\mathrm{mod}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{array}{ll}2x+3y=1& (\mathrm{mod}26)\\ 7x+14y=2& (\mathrm{mod}26)\end{array}$

Put into an augmented matrix

$\left[\begin{array}{ccc}2& 3& 1\\ 7& 14& 2\end{array}\right]$

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

$\left[\begin{array}{ccc}2& 3& 1\\ 7& 14& 2\end{array}\right]\to \left[\begin{array}{ccc}1& 5& -1\\ 0& -7& 3\end{array}\right]$

$\begin{array}{rl}x+5y& =-1(\mathrm{mod}26)\\ -7y& =3(\mathrm{mod}26)\end{array}$

We can invert -1/7 mod 26:

$-\frac{1}{7}=-15=11(\mathrm{mod}26)$

$\begin{array}{rl}y& =3\cdot 11=7(\mathrm{mod}26)\\ x& =-36=16(\mathrm{mod}26)\end{array}$

Second Option

Cramer's rule

$(x,y)=(\frac{\left|\begin{array}{cc}1& 3\\ 2& 14\end{array}\right|}{\left|\begin{array}{cc}2& 3\\ 7& 14\end{array}\right|},\frac{\left|\begin{array}{cc}2& 1\\ 7& 2\end{array}\right|}{\left|\begin{array}{cc}2& 3\\ 7& 14\end{array}\right|})$

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

Theorem

You can solve $Ax=b(\mathrm{mod}n)$ for any $k\times k$ matrix of integers $A$ and any $k\times 1$ vector of integers $b$ when $\mathrm{G}\mathrm{C}\mathrm{D}(\left|A\right|,n)=1$