|
|
|
Prove the following:
for every positive integer k, there exists a positive integer m such that 3m + 5 is divisible by 2k.
Source: Arne Smeets, nrich.maths.org
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:
(32^1-1)/23 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=(32^(k-2)-1), and b=2k, which means a/b is an odd integer, so a(a+2)/(2b) is an odd integer.
a(a+2)/(2b) = (32^(k-1)-1)/2k+1, proving this little lemma.
Given an integer, k, suppose an "m" exists such that 3m+5 is divisible by 2k. 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 3m + 5 is divisible by 2k. This proof will prove the induction step, which is that for any k that is at least 3, an integer, n, exists such that 3n + 5 is divisible by 2k. Furthermore, you will get a hint of the value of n. Either n=m, which will be case 1, below, or else n=m+2k-2, which will be case 2.
Either (3m+5)/2k is even or odd. I'll consider these two cases separately. The first case is easy.
case 1: If (3m+5)/2k is even, then 3m+5 is is equal to 0 mod 2k+1, proving the induction step.
case 2: If (3m+5)/2k is odd, then so are these two integers:
(32^(k-2))(3m+5)/2k -- the product of two odd integers and
5(32^(k-2)-1)/2k -- another product of two odd integers (see the lemma, above)
(3m+2^(k-2)+5)/2k = (32^(k-2))(3m+5)/2k - 5(32^(k-2)-1)/2k, which is the difference of two odd integers, so
(3m+2^(k-2)+5)/2k is an even integer, so 3m+2^(k-2)+5 is divisible by 2k+1
Whew!
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 -- 3m+1 alternates between 2 and 4, mod 8, and 3m+3 alternates between 4 and 6, mod 8, so you'll never find a "k" that is 3 or larger such that 3m+1 or 3m+3 is divisible by 2k.
Alexander Monnas proposed a different method to prove that for any given k there exists an m such that: 3m+5�0 mod 2k.
First note that, since (3,2k)=1 we have from Euler's Totient Theorem that
3j(2^k)�1 mod 2k
j(2k)=2k-1, so
32^(k-1)�1 mod 2k
If d exists, where d<2k-1, such that 3d�1, then d must be divisor of 2k-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 2k, and this last term is 1, so (4-1)2^(k-2)�1, mod 2k.
The question of whether a smaller j would make (4-1)2^j�1, mod 2k 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 2k.
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 2k.
So, in particular, (4-1)2^(k-3)�1, mod 2k.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 2k;
The last term is 1, mod 2k, and the 2nd-last term is 2k-1, mod 2k.So (4-1)2^(k-3) is not equivalent to 1, mod 2k, 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 30,31,...,32^(k-2)-1 are incongruent residues, mod 2k.
For example if k=5 the 8 incongruent residues, mod 32, are
1 (30), 3 (31), 9 (32), 27 (33), 17 (34), 19 (35), 25 (36), 11 (37).
It now remains only to show that, for any given k, one of these residues must be -5, mod 2k.
First note that 3n+2-3n, mod 2k is a multiple of 8. (This follows from 3n+2-3n = 3n(32-30)) = 8*3n)
Since there are 2k-2 residues corresponding to powers of 3 (out of a total of 2k-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<2k-2 such that 3m�-5.
Sloan's A068531: (32^(k-2)-1)/2k = 1, 5, 205, 672605, 14476720225405, ... for k=3, 4, 5, ...
The webmaster and author of this Math Help site is Graeme McRae.