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{\mathbb{N}}$, where $\mathrm{G}\mathrm{C}\mathrm{D}(a,n)=1$, we have $a^{\varphi (n)}\equiv 1(\mathrm{mod}n)$

Proof

Consider the elements of $(\mathbb{\mathbb{Z}}/n\mathbb{\mathbb{Z}}{)}^{*}$: Call them $x_1,\dots ,x_{\varphi (n)}$.

Since $\mathrm{G}\mathrm{C}\mathrm{D}(a,n)=1$, this set of elements is equal to $\{a{x}_1,\dots ,a{x}_{\varphi (n)}\}$. This is because $\mathrm{G}\mathrm{C}\mathrm{D}(a,n)=1$ and $\mathrm{G}\mathrm{C}\mathrm{D}(x_i,n)=1$ imply that $\mathrm{G}\mathrm{C}\mathrm{D}(a\varphi (n),n)=1$.

Therefore, the numbers $a{x}_1,\dots ,a{x}_{\varphi (n)}$ are all relatively prime to $n$. Moreover, $a{x}_i\equiv a{x}_j(\mathrm{mod}n)$ implies that $x_i\equiv x_j(\mathrm{mod}n)$ (since $\mathrm{G}\mathrm{C}\mathrm{D}(a,n)=1$), so $a{x}_1,\dots ,a{x}_{\varphi (n)}$ are all distinct

Therefore the product $\prod _{i=1}^{\varphi (n)}{x}_i=\prod _{i=1}^{\varphi (n)}a{x}_i$ can be simplified to $a^{\varphi (n)}\equiv 1(\mathrm{mod}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\le 100$-ish, grade-school is fastest. If $100\le n\le 1000$-ish, Karatsuba-Offman is fastest. Anything $n\ge 1000$-ish, FFT is fastest.

Counting Digits

• $\lfloor x\rfloor$ = floor of $x$ = greatest integer $\le x$
• $\lceil x\rceil$ = ceiling of $x$ = least integer $\ge x$

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

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

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

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

Square Roots Mod $n$

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

Square roots are:

• $x\equiv \pm 4(\mathrm{mod}19)$
• $x\equiv \pm 4(\mathrm{mod}23)$

Combined by CRT, we get

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