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) ?
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+2 k,m∊ℤ, or more precisely what restrictions need to be imposed on n for this equality to hold.
It turns out that m,n just need to be even.
Proposition 2 For n,m∊ℕ, x∊ℤ
x2n ≡ x2m (mod 3)
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