MATH 470 Lecture 17

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

End Exam 1 content

Midterm on Thursday

Euler's Theorem

Given 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, n \in \mathbb{N}} , where 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} , we have $a^{\phi (n)}\equiv 1{\pmod {n}}$

Proof

Consider the elements of 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 (\mathbb{Z}/n \mathbb{Z})^*} : Call them 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, \ldots, x_{\phi(n)}} .

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 \mathrm{GCD}(a,n) = 1} , this set of elements is equal 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 \{ 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 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 \ge 1000} -ish, FFT is fastest.

Counting Digits

• 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 \left\lfloor x \right\rfloor} = floor of 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} = greatest 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 \le x}
• 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 \left\lceil x \right\rceil} = ceiling of 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} = least integer $\geq x$

Derive a simple explicit formula for the number of base-10 digits of 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 \in \mathbb{N}} .

Experimentally, it looks like 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 \left\lfloor \log_{10}{x} \right\rfloor + 1} works.

Indeed, 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 x} has 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} decimal digits, then 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 10^{k-1} \le x \le 10^k-1} .

In general, the number of base-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} digits of 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 \in \mathbb{N}} is $\left\lfloor {\frac {\ln {x}}{\ln {b}}}\right\rfloor +1$

Square Roots 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}

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

Square roots are:

• 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 \equiv \pm 4 \pmod{19}}
• 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 \equiv \pm 4 \pmod{23}}

Combined by CRT, we get

• ±4
• 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 \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}}