All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars
 Click to listen to the single ▶Support album on Kickstarter perplexus dot info

 Many Multiples (Posted on 2012-04-30)
Prove that infinitely many numbers in the sequence {2012, 20122012, 201220122012, 2012201220122012,....} are multiples of 101.

 No Solution Yet Submitted by K Sengupta Rating: 4.0000 (2 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
 solution (spoiler) | Comment 2 of 8 |

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

 Search: Search body:
Forums (0)