Prove that infinitely many numbers in the sequence
{2012, 20122012, 201220122012, 2012201220122012,....} are multiples of 101.
Each transition to the next number in the series is accomplished by multiplying by 10,000 and adding 2012.
In modulus 101, 10,000 is congruent to 1, so when multiplying by 10,000, the value mod 101 doesn't change. The GCD between 2012 and 101 is 1; in other words they are relatively prime, as 2012 = 2 * 2 * 503 and 101 is prime. Thus is it a matter of time (iterations) before any value mod 101 repeats, as that value goes up by 93 (or down by 8) each iteration. After 101 iterations the modular value repeats after having gone through all 101 values.
Via Euclidean algorithm:
2012 = 0 * 101 + 1 * 2012
101 = 1 * 101 + 0 * 2012
93 = -19 * 101 + 1 * 2012
8 = 20 * 101 - 1 * 2012
5 = -239 * 101 + 12 * 2012
3 = 259 * 101 - 13 * 2012
2 = -498 * 101 + 25 * 2012
1 = 757 * 101 - 38 * 2012
0 = -2012 * 101 + 101 * 2012
Since 1 = 757 * 101 - 38 * 2012 and -1 = -757 * 101 + 38 * 2012,
-93 = -70401 * 101 + 3534 * 2012
and
0 = -2012 * 101 + 101 * 2012
= -68408 * 101 + 3434 * 2012
and, subtracting,
-93 = -1993 * 101 + 100 * 2012
so,after 100 iterations, when you have 101 copies of 2012 concatenated, you'll have a multiple of 101.
In hindsight, 0 is a multiple of 101, and since the values mod 101 repeat every 101 iterations, every multiple of 101 concatenations of 2012 will be a multiple of 101.
|
|
Posted by Charlie
on 2012-04-30 14:54:09 |
solution (spoiler)
