All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars    
perplexus dot info

Home > Numbers > Sequences
Many Multiples (Posted on 2012-04-30) Difficulty: 2 of 5
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 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
Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (8)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2014 by Animus Pactum Consulting. All rights reserved. Privacy Information