1
$\begingroup$

Can it be done by hand i.e. to find the remainder when $213987654213473846989272654857367287454572836418486364$ is divided by $48$?

$\endgroup$

closed as off-topic by Andrés E. Caicedo, apnorton, graydad, user223391, Claude Leibovici Jun 10 '15 at 6:28

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "This question is not about mathematics, within the scope defined in the help center." – Andrés E. Caicedo, apnorton, graydad, Community, Claude Leibovici
If this question can be reworded to fit the rules in the help center, please edit the question.

  • 2
    $\begingroup$ Sure it can be by hand, why not? $\endgroup$ – Hagen von Eitzen Jun 9 '15 at 19:59
  • $\begingroup$ What do you mean "by hand"? You could use long division. What's the background? $\endgroup$ – Karl Jun 9 '15 at 19:59
  • 5
    $\begingroup$ Find the sum of the digits mod $3$, then find the number created by the last $4$ digits mod $16$, then use Chinese Remainder Theorem. $\endgroup$ – user26486 Jun 9 '15 at 19:59
  • 4
    $\begingroup$ $6364 \text{mod}\ 16=12$ and $3\ |\ Number$, so by CRT, only possible answer is the number between 0 and 48, which is divisible by $3$ and leaves remainder $12$ on dividing by $16$ , such number is $12$ and hence your answer $\endgroup$ – Bhaskar Vashishth Jun 9 '15 at 20:13
  • 2
    $\begingroup$ I copied and pasted your question straight into Wolfram Alpha and it gave me the answer: $12$. You can also get the answer with a basic 10-digit calculator, and it doesn't take that much effort. With some understanding of congruences, you could easily calculate a googol or a googolplex or Graham's number modulo $48$. $\endgroup$ – user156970 Jun 9 '15 at 20:50
10
$\begingroup$

One way would be to perform a long division by $48$, which is not even that hard to do.

Another way is to compute the remainder modulo $3$, which can be obtained from the digit sum, and the remainder modulo $16$, which is determined only by the last four digits.

$\endgroup$
5
$\begingroup$

Let the large integer $N$. Since $48 = 2^4 \cdot 3$, by the Chinese Remainder Theorem, it suffices to find the remainder $N$ when is divided by $16$ and $3$.

Since $10^4$ is divisible by $16 = 2^4$, we only need to look at the last four digits to determine the remainder when $N$ is divided by $16$.

We can look at the sum of the digits of $N$ mod $3$ to get the remainder when $N$ is divided by $3$.

Both of these are easy to do by hand.

$\endgroup$
3
$\begingroup$

Hint $\ \begin{align} n\equiv a&\!\!\!\pmod 3\\ n\equiv b&\!\!\!\pmod {\color{#c00}{16}}\end{align}\!\!\!\!\overset{\ \ \rm CRT}\iff n\equiv b+16(a\!-\!b)\pmod{48},\ $ and $\ 2\mid 10\,\Rightarrow\,\color{#c00}{2^4}\!\mid 10^4,\,$

and, $\ {\rm mod}\ 3\!:\ 10\equiv 1\,\Rightarrow\, n = f(10)\equiv f(1)\equiv $ digit sum (casting out threes, like nines).

$\endgroup$
3
$\begingroup$

Let the giant number be $N$, thus sum of the digits is $276$ (yes, I calculated that by hand) and $48 = 2^4 \times 3$.

Now sum of digits is $276$, which tells us that it gives $0$ as remainder when divided by $3$ as $3$ divides $276$, so $N \bmod 3 = 0$.

Last four digits are $6364 = 16 \times 397 + 12$ (hardly five minutes, without calculator, I took around two).

Now $(16, 3) = 1$. Therefore Chinese remainder theorem tells us we need to find the number between $0$ and $48$ such that it is divisible by $3$ and leaves remainder $12$ when divided by $16$.

Only $12$ and $44$ leaves remainder $12$ when divided by $16$, but $44$ is not divisible by $3$.

Hence, the remainder is $12$.

$\endgroup$
  • $\begingroup$ You really don't need to find the explicit sum of the digits. Just keep reducing it mod $3$ as you count each digit one by one. $\endgroup$ – user26486 Jun 9 '15 at 20:28
  • $\begingroup$ You didn't mention 16 + 12 = 28. $\endgroup$ – Geoff Pointer Jun 10 '15 at 2:51
0
$\begingroup$

That certainly looks like a daunting number, but you can cut it down to a more manageable size, since what you're interested in is where it falls in relation to multiples of 48. Starting with the most significant digit (the leftmost) and moving to the right, add up the digits and delete them each time you accumulate to a multiple of 3, until you're left with five or four digits:

$54213473846989272654857367287454572836418486364$

$213473846989272654857367287454572836418486364$

$3473846989272654857367287454572836418486364$

$\ldots$

$86364$

This tells us that 2139876542134738469892726548573672874545728364184 is divisible by 3, and since 86364 is also divisible by 3, then so is 213987654213473846989272654857367287454572836418486364. It follows that 213987654213473846989272654857367287454572836418400000 is divisible by 16, a conclusion easily arrived at knowing that $10^4 = 2^4 \times 5^4$. Therefore we can focus our attention on 86364, a far more manageable number.

Is 86364 divisible by 16? It is not, it leaves a remained of 12. But $86364 - 12 = 86352$, which is divisible by 3 and by 16, and is therefore a multiple of 48. Thus the answer is 12.

What I have described here is neither the most elegant nor the most efficient way to get the answer. But it is the most basic (you don't need to know the Chinese remainder theorem, though it comes in handy for many different problems), second only to actually doing the long division.

$\endgroup$

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