Home Page ∙ Noel Posicion Computer Programmer

 

sublimitas EGO operor non votum transcendo

 

 

ύψος εγώ κάνω όχι ευχή σε πλεόνασμα

Basic Number Theory

Last updated: August 23, 2007

 

Let S = ∑^n-1_r=0 a^n-1-rb^r where a and b are real numbers and n is a positive integer.

 

Properties of S when a and b are odd numbers:

 

1)      S is an odd number if n is odd since S is a sum of n (odd) odd terms when n is odd

2)      S is an even number if n is even since S is a sum of n (even) odd terms when n is even

 

For convenience, denote S as S_o if n is odd and denote S as S_e if n is even.

 

Theorem 1: aⁿ – bⁿ = (a – b)S.

 

Proof by Mathematical Induction (PMI)

 

Let aⁿ – bⁿ = (a – b)S = (a – b) ∑^n-1_r=0 a^n-1-rb^r.

 

Case n = 1:

 

a – b    = (a – b)a^1-1-0b⁰ = (a – b)a⁰b⁰ = (a – b)(1)(1)

 

Case n > 1:

 

aⁿ – bⁿ  = (a – b)a^n-1-0b⁰ + (a – b) ∑^n-1_r=1 a^n-1-rb^r

                = (a – b)a^n-1 + (a – b) ∑^n-1_r=1 a^n-1-rb^r

                = aⁿ – ba^n-1 + (a – b) ∑^n-1_r=1 a^n-1-rb^r

 

Eliminate aⁿ and rearrange

 

ba^n-1 – bⁿ = (a – b) ∑^n-1_r=1 a^n-1-rb^r

 

Reindex

 

ba^n-1 – bⁿ = (a – b) ∑^n-2_r=0 a^n-2-rb^r+1

 

Finally, divide by b to get

 

a^n-1 – b^n-1 = (a – b) ∑^n-2_r=0 a^n-2-rb^r ■

 

Theorem 2a: f(aⁿ – bⁿ) > 1 if a and b are odd numbers and n is an even number.

 

Proof

 

f(aⁿ – bⁿ) = f((a – b)S_e) = f(a – b) + f(S_e)

 

Now f(a – b) ≥ 1 and f(S_e) ≥ 1 if a, b are odd and n is even.

 

Thus

 

f(aⁿ – bⁿ) = f((a – b)S_e) = f(a – b) + f(S_e) ≥ 2 > 1 ■

 

Theorem 2b: f(aⁿ + bⁿ) = 1 if a and b are odd numbers and n is an even number.

 

Proof

 

aⁿ + bⁿ = aⁿ – bⁿ + 2bⁿ

f(aⁿ + bⁿ) = {f(aⁿ – bⁿ), f(2bⁿ)}min = f(2bⁿ) = 1 ■

 

Theorem 3: f(aⁿ – bⁿ) = f(a – b) + f(a + b) + f(n) – 1 if a and b are odd numbers and n is an even number.

 

Proof

 

Let n = 2^f(n)m where m is an odd number.

 

Thus

 

aⁿ – bⁿ = (a^n/2 – b^n/2)(a^n/2 + b^n/2)

            = (a^n/4 – b^n/4)(a^n/4 + b^n/4)(a^n/2 + b^n/2), if f(n) > 1

            = (a^n/8 – b^n/8)(a^n/8 + b^n/8)(a^n/4 + b^n/4)(a^n/2 + b^n/2), if f(n) > 2

 

            …

 

= (a^m – b^m) Π^f(n)_i=1 (a^{n/(2^i)} + b^{n/(2^i)})

= (a^m – b^m)( a^{n/(2^f(n))} + b^{n/(2^f(n))}) Π^f(n)-1_i=1 (a^{n/(2^i)} + b^{n/(2^i)})

            = (a^m – b^m)(a^m + b^m) Π^f(n)-1_i=1 (a^{n/(2^i)} + b^{n/(2^i)})

 

If a^m – b^m = (a – b)S_o then  f(a^m – b^m) = a – b since S_o is an odd number (when m is odd).

 

Now, a^m + b^m = a^m – (-b)^m.

 

If  a^m + b^m = (a + b)S_o then f(a^m + b^m) = a + b since S_o is an odd number (when m is odd).

 

Thus, we have