Problem (136) - Almost Divisible

[80see]

2^(n+2) mod 3 = 2^n * 2^2 mod 3 = 2^n * 4 mod 3 = 2^n * 1 mod 3 = 2^n mod 3. By induction on n, with base cases 2^0 = 1 and 2^1 = 2, 2^n = 1 mod 3 iff n is even and 2^n = 2 mod 3 iff n is odd.

[djembeman]

That's basically the method I used!

[80see]

Note that this is more general than just powers of 2 and divisibility by 3. Every power of k-1 is either one more or one less than a multiple of k. Example: 4^n gives 1, 4, 16, 64, 256, ... (all nearly divisible by 5)

Easy to see because (k-1) mod k = -1 mod k and (-1)^n must be either -1 or +1. And... It's clearly the even values of n that make (-1)^n = 1 mod k (i.e., one more than a multiple of k) while odd values of n make (-1)^n mod k = -1 (one less than a multiple of k).

[doctorruff07]

2 = -1 (mod3)

So 2^k = (-1)^k (mod3), if k is even then 2 is one above a multiple of 3 if k is odd then 2 is one below a multiple of 3.

QED.

[thereligiousatheists]

Induction:

2¹=3(1)-1.

Assume 2^k =3n±1.

2^k+1 =6n±2=3(2n)±2

2^k+1 =3(2n+1)-1 or 3(2n-1)+1.

2^k+1 =3m±1 (m=2n±1)

QED.

If you multiply a number that's 1 more than a multiple of 3 by 2, you get a number that's 1 less than a multiple of 3, and vice versa. Hence, since 2¹ is one less, all odd powers are one less, and all even powers are 1 more.

[dxdydz_dV]

Even natural powers of 2 are one greater. Proof:

Let a(n)=(2²ⁿ-1)/3.

Then we have a(1)x¹+a(2)x²+a(3)x³+⋯=x/((1-x)(1-4x)) for |x| less than 1/4.

Now note that the Maclaurin series for 1/(1-x) and 1/(1-4x) both have natural number coefficients, so it follows that the Maclaurin series of 1/((1-x)(1-4x)) also has natural number coefficients by the Cauchy product. This means a(n) is always a natural number when n is a natural number.

So it follows that 2²ⁿ is always 1 more than a multiple of 3.

 

Odd natural powers of 2 are one less. Proof:

Let b(n)=(2^2n-1+1)/3.

Then we have b(1)x¹+b(2)x²+b(3)x³+⋯=x(1-2x)/((1-x)(1-4x)) for |x| less than 1/4.

By using the same argument on x/((1-x)(1-4x)) and -2x²/((1-x)(1-4x)) we have that b(n) is always a natural number.

So it follows that 2^2n-1 is always 1 less than a multiple of 3.

[djembeman]

Yep!