13
$\begingroup$

101102103104105106..............149150. What is the remainder when divided by 9?

My Approach

I think the remainder will be $0$.

Because I think all numbers are in multiplication and if I divide $108/9=0$ remainder, and thus multiplication of all these numbers will be $0$.

Can anyone guide me? Is my approach correct?

$\endgroup$
  • 7
    $\begingroup$ Question is likely about number which is recorded in base 10 as "101102103...150" (that is, number is exactly 450 digits long). $\endgroup$ – Abstraction Nov 17 '15 at 9:53
  • 1
    $\begingroup$ Can you explain where you get 108 from? $\endgroup$ – Ian Miller Nov 17 '15 at 9:58
  • $\begingroup$ As @Abstraction commented, you should not think of it as a multiplication. Try to understand what reduction modulo $9$ does to a number in decimal basis... (you can start with numbers with few digits...) $\endgroup$ – b00n heT Nov 17 '15 at 9:58
  • 4
    $\begingroup$ @Abstraction I seem to follow your idea, but wouldn't the number be 150 digits long, not 450? 101 102 103 ... 150, so $3\cdot50=150$? Well, ok the OP says multiplication, but it seems to me more like concatenation so I am confused. $\endgroup$ – Mirko Nov 17 '15 at 15:09
  • $\begingroup$ @Mirko Sorry, somehow thought there are 150 numbers from 101 to 150, my bad. $150$ digit long, of course. $\endgroup$ – Abstraction Nov 17 '15 at 15:39
36
$\begingroup$

$101102...149150=101(9999...9+1)+102(999...9+1)+...+149(999+1)+150$

$\equiv101+102+...+150\pmod{9}\equiv2+3+...+51\pmod{9}\equiv{(53)(50)\over2}=1325\equiv2\pmod{9}$

$\endgroup$
  • 2
    $\begingroup$ And here I was looking around the office for a very, very long piece of paper... $\endgroup$ – corsiKa Nov 17 '15 at 19:13
  • $\begingroup$ Why 9999...9 +1? $\endgroup$ – user253751 Nov 18 '15 at 3:17
  • 2
    $\begingroup$ $101000..0=101\cdot 1000...0=101\cdot(9999...9+1)$. $\endgroup$ – cr001 Nov 18 '15 at 3:24
  • $\begingroup$ @cr001 wouldn't $1000...0 = 999...9+1$? $\endgroup$ – corsiKa Nov 18 '15 at 21:13
  • 3
    $\begingroup$ Uhm, he said that. $\endgroup$ – Leif Willerts Nov 18 '15 at 22:12
29
$\begingroup$

Assuming you mean this number:

101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150

As you seem to know, the remainder when dividing by 9 is equal to the remainder why the sum of the digits is divided by 9. In this case the sum of the digits is 380. The sum of those digits is 11 so the remainder will be 2.

$\endgroup$
  • $\begingroup$ I think you should consider not including all of the $150$ digits, since it does not fit the text width - at least not on my computer ... $\endgroup$ – String Nov 17 '15 at 10:13
  • $\begingroup$ Fits on mine... $\endgroup$ – Ian Miller Nov 17 '15 at 10:57
  • 19
    $\begingroup$ There is a horizontal scroll feature. $\endgroup$ – greggo Nov 17 '15 at 11:58
  • 6
    $\begingroup$ Code blocks automatically allow for scrolling @IanMiller. All that was added to the front of the number was 4 spaces. $\endgroup$ – James Webster Nov 17 '15 at 15:36
  • 2
    $\begingroup$ This should be the correct answer! $\endgroup$ – Shiplu Mokaddim Nov 18 '15 at 4:41
16
$\begingroup$

Since $10^n=(9+1)^n\equiv 1\pmod9$ we have $$ \begin{align} \underbrace{101102...150}_{150\text{-digit number}}&\equiv 101+102+...+150\\ &=50\cdot\frac{101+150}{2}\\ &=6275\\ &\equiv 6+2+7+5\\ &\equiv 2\pmod9 \end{align} $$

$\endgroup$
  • 2
    $\begingroup$ I think $25\times 251$ is not $860$. $\endgroup$ – cr001 Nov 17 '15 at 10:05
  • $\begingroup$ @cr001: Yes, indeed. I do not know what got into my typing in Wolfra|Alpha :) $\endgroup$ – String Nov 17 '15 at 10:06
7
$\begingroup$

There's a bunch of different answers here. Looking at barak manos' idea is one way of doing it, but there is an arithmetical error.

Remember that the remainder mod 9 is invariant under taking sum of digits. That is, if we write a decimal expansion as $$ k = d_1d_2d_2\cdots d_{n-1}d_n $$ then $k \equiv \sum_{j=1}^n d_j \pmod 9$. So let's look at the digit sum in question. We have a concatenation of the numbers 101 through to 150. The first digit 1 occurs 50 times, so this will add 50 to our total. The remaining digits are the digit sums of 1 through to 50.

As is stated in the other answer, the ones column will produce each of the numbers 1 through 9 exactly five times; this will add $5(1 + \cdots + 9) = 225$ to our digit sum.

The tens column will add 0 nine times, 1 ten times, 2 ten times, 3 ten times 4 ten times, and 5 once. This adds up to $10(1 + 2 + 3 + 4) + 5 = 105$.

So our digit sum will be $$ 50 + 225 + 105 = 380 $$ Applying digit sum again we get $3 + 8 = 11$. So in the end we have $$ k \equiv 380 \equiv 11 \equiv 2 \pmod 9 $$

$\endgroup$
5
$\begingroup$

Yet another possible shortcut is to notice that the sum of any 9 consecutive numbers is divisible by 9. Intuitively, one of the 9 numbers must be a multiple of 9, and the rest form symmetrical pairs around it whose mod 9 remainders "cancel out". Or, see Prove the sum of any $n$ consecutive numbers is divisible by $n$ (when $n$ is odd). for a more formal proof.

Since the mod 9 remainder of the given number is the same as that of the sum of the 50 consecutive numbers 101 + 102 + ... +150, 5 groups of 9 consecutive numbers can be dropped from that sum as having mod 9 remainders of 0. Choosing to drop the last 45 numbers leaves 101 + 102 + 103 + 104 + 105 which has a mod 9 remainder of 2.

[ EDIT ] To elaborate the "mod 9 remainder of the given number is the same as that of the sum of the 50 consecutive numbers 101 + 102 + ... +150".

$10 ≡ 1\;(mod\;9)$ thus $10^2 = 10 * 10 ≡ 1 * 1 = 1\;(mod\;9)$ and by induction $10^n ≡ 1\;(mod\;9)$ for all $n >= 0$. The given number is $101 * 10^{148} + 102 * 10^{145} + ... + 149 * 10^3 + 150$, and since all factors $10^k ≡ 1\;(mod\;9)$, the sum simplifies $(mod\;9)$ to $101 + 102 + ... + 150$.

$\endgroup$
  • $\begingroup$ You should explain why "mod 9 remainder of the given number is the same as the sum of the $50$ consecutive numbers"? Perhaps you could explain that $1000^n = 9(\sum_{k=0}^{3n-1}10^{k}) +1$ $\endgroup$ – Nex Nov 18 '15 at 5:03
  • $\begingroup$ @Nex that was used and explained at length in some of the other answers, which I didn't want to repeat. But you're right, and I made an edit to spell it out. $\endgroup$ – dxiv Nov 18 '15 at 5:41
3
$\begingroup$

Here's another approach which allows us to determine the $\pmod9$ of any consecutive sum with at most four additions and at most 3 $\pmod x$ evaluations. Quite efficient!

For any three consecutive numbers, the remainder of their sum and nine will be the same as the next three consecutive (because each element in the triplet is three more than that same position in the previous triplet, and $3+3+3=9$).

We know our three numbers are $101+102+103=306\equiv0\pmod9$. Thus each consecutive triplet will also be $\equiv0\pmod9$. Evaluating the remaining elements (in this case 2) results in elements $$149+150=299\equiv2\pmod9$$.

If the number of elements was divisible by three, we could omit the last part because there would be no remaining elements. If our triplet was a non-zero remainder, we would have to add that to the sum of the remaining elements before modding. (We could add it to the resulting mod but if it goes over 9 we would have to mod again which would be inefficient...)

If you're wondering where the third $\pmod x$ evaluation is, we have to do a $n \pmod 3$ to determine how many elements are remaining.

$\endgroup$
  • $\begingroup$ It's even more efficient when you combine this with the knowledge that the sum of digits = original number mod $9$. So it isn't necessary to do the full sum of $101+102+103$, just add the digits to get $9 \equiv 0 \mod 9$, and for $149 + 150$, throw out the $9$, and the $4 + 5 = 9$, and you are left with two $1$s, for a result of $2 \mod 9$ $\endgroup$ – Paul Sinclair Nov 18 '15 at 16:40
  • $\begingroup$ That puts multiple adds and a lot more logic. I don't think that's more efficient at all in terms of number of operations. Specifically, all those adds scale higher with the number of elements while my version doesn't. $\endgroup$ – corsiKa Nov 18 '15 at 17:11
  • $\begingroup$ Not all additions are created equal. Every addition and every bit of logic I did was just a shortcutting of the process of the 3-digit additions you required to skip some steps that made no difference in the end. If you just count operations, then a "more efficient" solution is to divide the original 150 digit number by 9, discard the integer portion, and multiply the remainder by 9. Three operations total. But that measure is obviously flawed. $\endgroup$ – Paul Sinclair Nov 18 '15 at 20:36
2
$\begingroup$

The summation of digits at hundreds place is $50$ then the summation of digits at units place is $45.5=225$ notice the last digits they are $1,2,3,4,5,6,7,8,9,0 $ they are repeated $5$ times And summation of digits at tens place is $10+20+30+40+5=105$ so summation of all is $50+105+225=380$ so remainder is $2$. Hope this hepls you.

$\endgroup$
1
$\begingroup$

In base $10$, you can sum the digits in an iterative way. E.g.

193 -> 13 -> 4 (193 is not divisible by 9).
198 -> 18 -> 9 (198 is divisible by 9).

Due to this base is $10$, you can even add the number by parts and "reduce" them later. Since I could reduce a number like this:

101102 -> 101 + 102 -> 203 -> 5 (not divisible by 9)

I could make it in a bigger scale. Lets just explain why we could reduce like that:

101102 = 101*999 + 101 + 102 -> 101 + 102
(we discard the first term since it is already divisible by 9)

And we can do that for any order of digits, like:

101102103 = 101*999999 + 101 + 102*999 + 102 + 103 -> 101 + 102 + 103
(the *999999 and *999 terms were discarded since they are already divisible by 9)

So we can reduce your big number to:

101 + ... + 150 = 251 * 50 / 2 = 6275 -> 20 -> 2

The remainder is $2$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.