MATH 470 Lecture 17

From Notes
Jump to navigation Jump to search

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

End Exam 1 content


Midterm on Thursday

Euler's Theorem

Given a,n∈ℕ, where GCD(a,n)=1, we have aϕ(n)≡1(modn)

Proof

Consider the elements of (ℤ/nℤ)*: Call them x1,…,xϕ(n).

Since GCD(a,n)=1, this set of elements is equal to {ax1,…,axϕ(n)}. This is because GCD(a,n)=1 and GCD(xi,n)=1 imply that GCD(aϕ(n),n)=1.

Therefore, the numbers ax1,…,axϕ(n) are all relatively prime to n. Moreover, axi≡axj(modn) implies that xi≡xj(modn) (since GCD(a,n)=1), so ax1,…,axϕ(n) are all distinct

Therefore the product ∏i=1ϕ(n)xi=∏i=1ϕ(n)axi can be simplified to aϕ(n)≡1(modn).


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(n2)
  • Kanatsuba-Offman: O(n1.58)
  • Fast Fourier Transform: O(nlog⁡nlog⁡log⁡n)

However, if n≤100-ish, grade-school is fastest. If 100≤n≤1000-ish, Karatsuba-Offman is fastest. Anything n≥1000-ish, FFT is fastest.

Counting Digits

  • ⌊x⌋ = floor of x = greatest integer ≤x
  • ⌈x⌉ = ceiling of x = least integer ≥x

Derive a simple explicit formula for the number of base-10 digits of x∈ℕ.

Experimentally, it looks like ⌊log10x⌋+1 works.

Indeed, if x has k decimal digits, then 10k−1≤x≤10k−1.

In general, the number of base-b digits of x∈ℕ is ⌊ln⁡xln⁡b⌋+1

Square Roots Mod n

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

Square roots are:

  • x≡±4(mod19)
  • x≡±4(mod23)

Combined by CRT, we get

  • ±4
  • ±4⋅23(123mod19)∓4⋅19(119mod23)≡±42(mod437)