"The poet only asks to get his head into the heavens. It is the logician who seeks to get the heavens into his head. And it is his head that splits." G.K. Chesterton

## Monday, April 25, 2011

### Number Theory 2

In the previous post we derived an interesting (although rather basic) result from the fact that:

xn + xn+m = 2k

For n∊ℤ+, k,x∊ℤ, and m∊ℕ. That result entails: xn xn+m (mod 2). Can we get a similar result for mod 3? That is, what are the m,n∊ℤ such that xn xm (mod 3) ?
It turns out that m,n just need to be even.
Proposition 2   For n,m∊ℕ, x∊ℤ
x2n x2m (mod 3)
Proof
We have three cases: x=3k, x=3k+1 and x=3k+2  k∊ℤ. The first two are identical to mod 2 cases proven in the previous post i.e. ( 3k )n, and  ( 3k+1 )n factorize to be multiples of 3 and multiples of 3, +1 respectively. All that remains to show is that ( 3k+2 )n = 3m+k,m∊ℤ, or more precisely what restrictions need to be imposed on n for this equality to hold.
By The Binomial Theorem all the terms except the constant factorize as multiples of 3, but we're left with a 2n constant term at the end. We want it to have the form 3m+2, so the first term can be factorized and the second to be the reminder.
Consider 2n-2+2, so the question remains to find n such that 3|2n-2 = 2( 2n-1-1 ).
Note that if 3|2n-1-1then 3| 2( 2n-1-1 ). The following lemma gives us the required result:

Lemma: 3| 22n-1 for n∊ℕ
Proof by induction on n:
22n-1 = 4n-1
Base case: 40-1 = 1-1 = 0 = 3(0)
Now suppose that if 3|4k-1 implies 3|4k+1-1 for arbitrary k∊ℕ then 3|4n-1 ∀n∊ℕ.
In other words is  4k+1-1 divisible by 3 given that 4k-1 is?
4k+1-1 =  4k+1- 4+3 = 4( 4k-1 ) +3 = 4(3j) +3 (by inductive hypothesis) = 3( 4j +1 ) j∊ℤ
Hence 3|4n-1for ∀n∊ℕ q.e.d.
Incidently this is also a result about Mersenne Numbers. It says that at least half of the Mersenne Numbers are divisible by 3.

Now returning to our original discussion the lemma gives us m such that 3| 2( 2m-1 ), namely m needs to be even. Since no restrictions on parity of m were necessary in the 3k, and 3k+1 cases, it follows that
xn xm (mod 3) iff n and m are even. Or just, for any n,m ∊ℕ,  x2n x2m (mod 3), as required.

Corollary 1.1
Propositions 1 and 2 jointly give n, m > 0, |x| > 2:
x2n x2m (mod 6)

Example. This result guarantees that  |x| > 2, a∊ℤ , i > 0, and ∀n∊ℕ

#### 1 comment:

Mariusz Popieluch said...

There some obvious bounds declarations missing on the variables of the lemmas. Fixed now.