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

*x*+

^{n}*x*

^{n+m}= 2

*k*

For

*n*∊ℤ^{+},*k*,*x*∊ℤ, and*m*∊ℕ. That result entails:*x*≡^{n}*x*^{n+m}(mod 2). Can we get a similar result for mod 3? That is, what are the*m*,*n*∊ℤ such that*x*≡^{n}*x*^{m}(mod 3) ?It turns out that

*m*,*n*just need to be even.**Proposition 2**

*For*

*n,m*∊ℕ,

*x*∊ℤ

*x*

^{2}

*≡*

^{n}*x*

^{2m}(mod 3)

**Proof**

*x*=3

*k*,

*x*=3

*k*+1 and

*x*=3

*k*+2

*k*∊ℤ. The first two are identical to mod 2 cases proven in the previous post i.e. ( 3

*k*)

*, and ( 3*

^{n}*k+1*)

*factorize to be multiples of 3 and multiples of 3, +1 respectively. All that remains to show is that ( 3*

^{n}*k+2*)

*= 3*

^{n}*m+*2

*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 2

^{n}constant term at the end. We want it to have the form 3

*m+*2, so the first term can be factorized and the second to be the reminder.

Consider 2

^{n}-2+2, so the question remains to find n such that 3|2

^{n}-2 = 2( 2

^{n-1}-1 ).

Note that if 3|2

^{n-1}-1then 3| 2( 2

^{n-1}-1 ). The following lemma gives us the required result:

Lemma: 3| 2

^{2n}-1 for ∀n∊ℕ

Proof by induction on

*n*:

2

^{2n}-1 = 4

^{n}-1

Base case: 4

^{0}-1 = 1-1 = 0 = 3(0)

Now suppose that if 3|4

^{k}-1 implies 3|4

^{k+1}-1 for arbitrary k∊ℕ then 3|4

^{n}-1 ∀n∊ℕ.

In other words is 4

^{k+1}-1 divisible by 3 given that 4

^{k}-1 is?

4

^{k+1}-1 = 4

^{k+1}- 4+3 = 4( 4

^{k}-1 ) +3 = 4(3

*j*) +3 (by inductive hypothesis) = 3( 4

*j*+1 )

*j*∊ℤ.

Hence 3|4

^{n}-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( 2

^{m}-1 ), namely

*m*needs to be even. Since no restrictions on parity of

*m*were necessary in the 3

*k*, and 3

*k*+1 cases, it follows that

## 1 comment:

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

Post a Comment