MATH 470 Lecture 17

« previous | Tuesday, March 19, 2013 | next »

End Exam 1 content

Midterm on Thursday

Euler's Theorem

Given $a,n\in \mathbb {N}$, where $\mathrm {GCD} (a,n)=1$, we have $a^{\phi (n)}\equiv 1{\pmod {n}}$

Proof

Consider the elements of $(\mathbb {Z} /n\mathbb {Z} )^{*}$: Call them $x_{1},\ldots ,x_{\phi (n)}$.

Since $\mathrm {GCD} (a,n)=1$, this set of elements is equal to $\{a\,x_{1},\ldots ,a\,x_{\phi (n)}\}$. This is because $\mathrm {GCD} (a,n)=1$ and $\mathrm {GCD} (x_{i},n)=1$ imply that $\mathrm {GCD} (a\,\phi (n),n)=1$.

Therefore, the numbers $a\,x_{1},\ldots ,a\,x_{\phi (n)}$ are all relatively prime to $n$. Moreover, $a\,x_{i}\equiv a\,x_{j}{\pmod {n}}$ implies that $x_{i}\equiv x_{j}{\pmod {n}}$ (since $\mathrm {GCD} (a,n)=1$), so $a\,x_{1},\ldots ,a\,x_{\phi (n)}$ are all distinct

Therefore the product $\prod _{i=1}^{\phi (n)}x_{i}=\prod _{i=1}^{\phi (n)}a\,x_{i}$ can be simplified to $a^{\phi (n)}\equiv 1{\pmod {n}}$.

Complexity

The devil is in the details: practical complexity depends on the Big-Oh constants!

For example: The main algorithms for multiplications:

• Grade school: $O(n^{2})$
• Kanatsuba-Offman: $O(n^{1.58})$
• Fast Fourier Transform: $O(n\,\log {n}\,\log {\log {n}})$

However, if $n\leq 100$-ish, grade-school is fastest. If $100\leq n\leq 1000$-ish, Karatsuba-Offman is fastest. Anything $n\geq 1000$-ish, FFT is fastest.

Counting Digits

• $\left\lfloor x\right\rfloor$ = floor of $x$ = greatest integer $\leq x$
• $\left\lceil x\right\rceil$ = ceiling of $x$ = least integer $\geq x$

Derive a simple explicit formula for the number of base-10 digits of $x\in \mathbb {N}$.

Experimentally, it looks like $\left\lfloor \log _{10}{x}\right\rfloor +1$ works.

Indeed, if $x$ has $k$ decimal digits, then $10^{k-1}\leq x\leq 10^{k}-1$.

In general, the number of base-$b$ digits of $x\in \mathbb {N}$ is $\left\lfloor {\frac {\ln {x}}{\ln {b}}}\right\rfloor +1$

Square Roots Mod $n$

Find the square roots of 16 mod 437 = 19 · 23.

Square roots are:

• $x\equiv \pm 4{\pmod {19}}$
• $x\equiv \pm 4{\pmod {23}}$

Combined by CRT, we get

• ±4
• $\pm 4\cdot 23\left({\frac {1}{23}}\mod {19}\right)\mp 4\cdot 19\left({\frac {1}{19}}\mod {23}\right)\equiv \pm 42{\pmod {437}}$