Powers of 3 and Powers of 2

Prove the following:

for every positive integer k, there exists a positive integer m such that 3^m + 5 is divisible by 2^k.

Source: Arne Smeets, nrich.maths.org

Lemma: (3^{2^(k-2)}-1)/2^k is an odd integer whenever k is at least 3.

This sequence is Sloan's A068531: 1, 5, 205, 672605, 14476720225405, ...

The proof of this lemma begins with the observation that when k=3, it is true:

(3^{2^1}-1)/2³ is 8/8 = 1, an odd integer.

Next, observe that if b is a power of 2 and is at least 8, and a/b is an odd integer, then a+2 is divisible by 2 but not by any higher power of 2.

So a(a+2)/(2b) = (a/b) * (a+2)/2, the product of odd integers, must also be an odd integer.

If a=(3^{2^(k-2)}-1), and b=2^k, which means a/b is an odd integer, so a(a+2)/(2b) is an odd integer.

a(a+2)/(2b) = (3^{2^(k-1)}-1)/2^k+1, proving this little lemma.

Proof by Induction on k

Given an integer, k, suppose an "m" exists such that 3^m+5 is divisible by 2^k.  This is true for k=1,2,3, which can be shown by picking m=1.

Now, the basis for the induction: if k=3, then an m exists (m=1) such that 3^m + 5 is divisible by 2^k.  This proof will prove the induction step, which is that for any k that is at least 3, an integer, n, exists such that 3ⁿ + 5 is divisible by 2^k.  Furthermore, you will get a hint of the value of n.  Either n=m, which will be case 1, below, or else n=m+2^k-2, which will be case 2.

Either (3^m+5)/2^k is even or odd.  I'll consider these two cases separately. The first case is easy.

case 1: If (3^m+5)/2^k is even, then 3^m+5 is is equal to 0 mod 2^k+1, proving the induction step.

case 2: If (3^m+5)/2^k is odd, then so are these two integers:

(3^{2^(k-2)})(3^m+5)/2^k -- the product of two odd integers and
5(3^{2^(k-2)}-1)/2^k -- another product of two odd integers (see the lemma, above)

(3^{m+2^(k-2)}+5)/2^k = (3^{2^(k-2)})(3^m+5)/2^k - 5(3^{2^(k-2)}-1)/2^k, which is the difference of two odd integers, so

(3^{m+2^(k-2)}+5)/2^k is an even integer, so 3^{m+2^(k-2)}+5 is divisible by 2^k+1

Whew!

Additional Notes on the Induction Proof

The number, 5, used in this puzzle isn't special.  Any odd number that is equivalent to 5 or 7 mod 8 will work just as well.   The reason 1 and 3 don't work is that you can't get the "induction engine" started -- 3^m+1 alternates between 2 and 4, mod 8, and 3^m+3 alternates between 4 and 6, mod 8, so you'll never find a "k" that is 3 or larger such that 3^m+1 or 3^m+3 is divisible by 2^k.

A Different Approach

Alexander Monnas proposed a different method to prove that for any given k there exists an m such that: 3^m+5º0 mod 2^k.

First note that, since (3,2^k)=1 we have from Euler's Totient Theorem that

3^{j(2^k)}º1 mod 2^k

j(2^k)=2^k-1, so

3^{2^(k-1)}º1 mod 2^k

If d exists, where d<2^k-1, such that 3^dº1, then d must be divisor of 2^k-1.

By considering the expansion of (4-1)^{2^j}, it is apparent that when j=k-2, every term of the expansion with the exception of the last term is 0, mod 2^k, and this last term is 1, so (4-1)^{2^(k-2)}º1, mod 2^k.

The question of whether a smaller j would make (4-1)^{2^j}º1, mod 2^k is a bit trickier, but the answer is no.  Here's why.

Suppose a j<k-2 exists such that (4-1)^{2^j}º1, mod 2^k.
In that case, squaring both sides of this equivalence, we see that
     (4-1)^{2^(j+1)}º1, (4-1)^{2^(j+2)}º1, etc., all mod 2^k.
So, in particular, (4-1)^{2^(k-3)}º1, mod 2^k.

When j=k-3, every term of the expansion of (4-1)^{2^j}, with the exception of the last two terms are 0, mod 2^k;
The last term is 1, mod 2^k, and the 2^nd-last term is 2^k-1, mod 2^k.

So (4-1)^{2^(k-3)} is not equivalent to 1, mod 2^k, a contradiction.

It is apparent, now, that the smallest j which results in (4-1)^{2^j}º1 is j=k-2.

We thus have that, for any given k, the numbers 3⁰,3¹,...,3^{2^(k-2)-1} are incongruent residues, mod 2^k.

For example if k=5 the 8 incongruent residues, mod 32, are
1 (3⁰), 3 (3¹), 9 (3²), 27 (3³), 17 (3⁴), 19 (3⁵), 25 (3⁶), 11 (3⁷).

It now remains only to show that, for any given k, one of these residues must be -5, mod 2^k.

First note that 3ⁿ⁺²-3ⁿ, mod 2^k is a multiple of 8.  (This follows from 3ⁿ⁺²-3ⁿ = 3ⁿ(3²-3⁰)) = 8*3ⁿ)

Since there are 2^k-2 residues corresponding to powers of 3 (out of a total of 2^k-1 odd residues), and since 1 and 3 are always two such residues, it follows that all the odd number residues (8n+1) and (8n+3) correspond to the powers of 3.  Hence there exists an m, 0<=m<2^k-2 such that 3^mº-5.

Internet References

Sloan's A068531: (3^{2^(k-2)}-1)/2^k = 1, 5, 205, 672605, 14476720225405, ... for k=3, 4, 5, ...

Related pages in this website

Euler's Totient Theorem

The webmaster and author of the Math Help site is Graeme McRae.
     [home]  [email]  [search]  [Links to Math Sites]  [Whiteboard]