Problem Solving

I know this question is not from the Gmat syllabus , But just wondering How to solve this one.


Let N = 121212 �� upto 300 digits. What is the remainder when N is divided by 999?


12

121

216

666

Hi there,

We know that N = 999Q + R, where Q is a positive integer and R is an integer such that 0<= R <= 998.

We look for the value of R, for sure.

The number N is formed by fifty '121212' "side-by-side blocks", each one of them is divisible by 9 (because of the sum of its digits), therefore N itself is divisible by 9 (same argument).

Conclusion: R is divisible by 9, because R = N - 999Q (difference of two multiples of 9 is also a multiple of 9).

From the alternatives offered, the answer must be (D) or (E).

So we will have to be a bit more careful/profound in our analysis!

> if R = 216, N = 999Q + 216 = 9 (111Q+24) = 9 * 3 * (37Q + 8) would imply N divisible by 27
> if R = 666, N = 999Q + 666 = 111 (9Q+6) = 111*3*(3Q+2) = 3*37*3*(3Q+2) would imply N is divisible by 9 but NOT by 27...

Please note that dividing one block '121212' by 9 you get 13468 (sum of digits 22) and if you divide two blocks of '121212' by 9 you get almost the same: 13468013468 (sum of digits 2*22) ... "therefore" 50 blocks '121212' (N) divided by 9 will have the following "structure": 13468013468013468... (49 zeros included and sum of digits 50*22).

From the fact that N divided by 9 has sum of digits 1,100 that is NOT divisible by 3, that means N is divisible by 9 but not by 27... therefore the answer is (D).

Regards,
Fabio.

goyalsau wrote:I know this question is not from the Gmat syllabus , But just wondering How to solve this one.


Let N = 121212 �� upto 300 digits. What is the remainder when N is divided by 999?


12

121

216

666

When you see this type of problem try looking for some patterns. Here is a pattern :

R(12/999) = 12
R(12*10^2/999) = 201
R(12*10^4/999) = 120
.............
This pattern (remainder being 12,201 and 120 for every 3nth, 3n+1th and 3n+2th member) is repeating next 50 times in the current problem.

R[(12+201+120)*50/999] = R[333*50/999] = R[333*(3*16+2)/999]
= R[333*2/999] = 666

(I have used some basic remiander rule to reduce the problem, which is in the GMAT syllabus : )
{If the remainder 333 is accumulated 3n times, then the remainder of R[333*3n/999] = 0}
R[333*2/999] = 666 {Remainder accumulated two times only, 333+333}.

fskilnik wrote:
Please note that dividing one block '121212' by 9 you get 13468 (sum of digits 22) and if you divide two blocks of '121212' by 9 you get almost the same: 13468013468 (sum of digits 2*22) ... "therefore" 50 blocks '121212' (N) divided by 9 will have the following "structure": 13468013468013468... (49 zeros included and sum of digits 50*22).

HI! Fabio, I am still trying to understand the explanation given by you , But i just want to share one information.


you were trying to test the divisibility of 121212 ---- 50 times by 27, All you you need to do is to add the sum of all the digits and divide it by 27, if the sum of digits is divisible by 27, Then Number is divisible by 27, If its not then the number is not divisible by 27,

Like in this case Case 121212 ----- 50 times ==== Sum of digits is 450 -------- 450 / 27 remainder is 18


In this case with the given options only 666 is the option when it is divided by 27 remainder is 18 .

666 = 24 * 27 + 18

I think this can also be a way to solve this problem.

Hi goyalsau! Thank you for your interest in my solution!!

goyalsau wrote:if the sum of digits is divisible by 27, Then Number is divisible by 27, If its not then the number is not divisible by 27,

You can use that for 3 and also for 9, but not for 27... (counter-) example: 1899 is not divisibly by 27 but the sum of its digits certainly is...

(Please note that 1,899 is divisible by 9 but the quotient 1,899/9 = 211 is NOT divisible by 3.)

Regards,
Fabio.

P.S.: if you want to decide whether a certain integer N is divisible by (say) 55, you can decide separately if N is divisible by 5 and if N is divisible by 11, just because 5 and 11 are relatively prime. To decide whether N is divisible by (say) 12, you may decide based on the divisibility by 3 and by 4 (they are relatively prime) but you cannot decide by the divisibility by (say) 2 and 6... do you see the difference?

Anurag@Gurome wrote:

Let N = 121212... up to 300 digits. What is the remainder when N is divided by 999?

12
121
216
666

Let me write the given 300 digit number as follows:

• 1212 ... 121212 = 1212 ... 121*1000 + 212
  = 1212 ... 2121*(999 + 1) + 212
  = 1212 ... 2121*999 + 1212 ... 2121 + 212
  = 999*(Something) + 1212 ... 2333

Now the first part i.e. 999*(Something) is divisible by 999. Thus the remainder is same as the remainder when 1212 ... 333 is divided by 999.

Now note that 1212 ... 333 has 297 digits. We have to find the remainder by repeating the same method as above. But don't worry. It's not much cumbersome as it looks like!

Let's do the 2nd step.

• 1212 ... 1212333 = 1212 ... 1212*1000 + 333
  = 1212 ... 1212*(999 + 1) + 333
  = 1212 ... 1212*999 + 1212 ... 1212 + 333
  = 999*(Something) + 1212 ... 1545

The number 1212 ... 1545 has 294 digits.

Now it is clear that in each step the number will be reduced by 3 digits. Thus there will be a total of 100 such steps. Also note that in each alternate step 121 and 212 will be removed and will be added to the remaining part. Thus in every 2 step 6 digit will be removed and (121+ 212) = 333 will be added.

Therefore after the 100 steps all the digits will be removed and 50 times 333 will remain. The remainder is nothing but the remainder when this reduced number is divided by 999.

The reduced number = 50*333 = (48 + 2)*333 = 48*333 + 2*333 = 16*999 + 666

Thus the remainder is 666.

The correct answer is D.

Great Work, Got it , I think this method can be used for any number of digits like up to 300 or 600...... or even more

You can we can calculate the quotient as well, How to do that??????? :roll:

fskilnik wrote:Hi goyalsau! Thank you for your interest in my solution!!

goyalsau wrote:if the sum of digits is divisible by 27, Then Number is divisible by 27, If its not then the number is not divisible by 27,

You can use that for 3 and also for 9, but not for 27... (counter-) example: 1899 is not divisibly by 27 but the sum of its digits certainly is...

(Please note that 1,899 is divisible by 9 but the quotient 1,899/9 = 211 is NOT divisible by 3.)

Regards,
Fabio.

P.S.: if you want to decide whether a certain integer N is divisible by (say) 55, you can decide separately if N is divisible by 5 and if N is divisible by 11, just because 5 and 11 are relatively prime. To decide whether N is divisible by (say) 12, you may decide based on the divisibility by 3 and by 4 (they are relatively prime) but you cannot decide by the divisibility by (say) 2 and 6... do you see the difference?

I am not feeling guilty at all, that i suggest you a shortcut, Which was completely wrong......... But i can say now this divisibility rule for 27 will remain long in my memory.............

thanks for your Help........ and You Rock.................... FABIO.......................

Thanks........

goyalsau wrote:I am not feeling guilty at all, that i suggest you a shortcut

You really SHOULDN´T! I would be the first (and happiest) one to accept a better approach, goyalsau.

goyalsau wrote:But i can say now this divisibility rule for 27 will remain long in my memory

Excellent. This is what really matters. Now you see why I had "a little more work" to finish my argument above!

Thank you for your nice compliment, goyalsau. I really hope YOU will "rock" in your GMAT, by the way!

Cheers,
Fabio.