1

Problem:

A factory uses 10 types of a box to package its product. They are numbered from 1 to 10. In box 10, 6 boxes of type 9 can be placed. In box 9, 6 boxes of type 8 can be placed, ... in box 2, 6 boxes of type 1 can be placed and finally in box 1, 6 products are placed. If we use boxes with a capacity of 215 products to package the products that are packaged in the box 10, how many products will be left over?

My attempt:

I figured out the hierarchy like a tree of degree 6. So, the box 10 can hold $6^{10}$ products. This is a huge number, how can I find its reminder to 215?

Ahmad
  • 383

2 Answers2

1

Chinese Remainder Theorem

$215 = 5*43$

$6\equiv 1 \mod 5$ so $6^{10}\equiv 1 \mod 5$. Which means $6^{10} \equiv 1 + 5M \mod 215$ for some $0 \le M < 43$.

$6^2 =36\equiv -7 \mod 43$ so $6^{4} \equiv 49 \equiv 6$ and, hey, that must mean $6^3 = -7*6 = -42 \equiv 1 \mod 43$.

So $6^{10} = (6^3)^3*6 \equiv 6 \mod 43$. So $6^{10} \equiv 6 + 43K \mod 215$ for some $0 \le K < 5$.

So we need $x \equiv 1\mod 5$ and $x \equiv 6\equiv \mod 43$. So $x = 1 + 5M = 6+43K$. And $0 \le x < 215$ so ($0 \le M < 43$ and $0\le K < 5$). CRT says there will be exactly one such solution.

Clearly $x = 1 + 5(1) = 6 + 43(0) = 6$ is one solution. CRT says it is the only solution.

Indeed the solutions have to be one of: $\{1,6,11,16,21,26,31,36,41,46,51,56,61,66,71,76,81,86,91,96,101,106,111,116,121,126,131,136,141,146,151,156,161,166,171,176,181,186,191,196,201,206,211\}$ and also one of $\{6,49,92,135,178\}$. The only number on both lists is $6$.

fleablood
  • 124,253
  • In your last line, how CRT results 6? I'm novice at this. – Ahmad Feb 17 '18 at 14:20
  • $6 \equiv 1 \mod 5$ and $6 \equiv 6 \mod 43$. That, I assumed, was obvious. Especially as we began with $6$ and not with $1$ and only got the $1$ because $6 \equiv 1 \mod 5$ in the first line. – fleablood Feb 17 '18 at 16:43
  • In general if you have $x\equiv a \mod n$ and $x \equiv b \mod m$ ($\gcd(m,n) =1$) it will not always be obvious what the one value of $x; 0 \le x < mn$ is. But you will have $x = a, a + n, a+2n, a + 3n....., a+(m-1)n$ and $x =b, b+m, b+2m, ..... , b + (n-1)m$ and in the lists there will be one number in common. with $1\mod 5$ yielding $1, 6, 11, ....,204,206, 211$ an $6\mod 43$ yielding $6,49, 92, 135, 178$ the only number is $6$. – fleablood Feb 17 '18 at 16:48
  • 1
    But it might not be obvious. But you will ge $x = a + kn = b + jm$ os $kn-jm = b-a$ which can be solved. so $x = 1 + 5k = 6 + 43j$ so $5k - 43j = 6-1 = 5$. Simple answer $k = 1$ and $j = 0$. $x = 1 + 51 = 6 43*0$. – fleablood Feb 17 '18 at 16:50
  • thank you. Do you know a good video or cheat sheet related to congruence? It doesn't need to be deep. I would like to enhance my speed on solving them. – Ahmad Feb 17 '18 at 17:50
  • No, I don't. Congruences and modular arithmetic really should be taught in elementary school before we teach how to non-modular arithmetic. In my opinion congruences and modular arithmetic are much much simpler and easier. Just spend the next day or two counting on your fingers and starting over when you get to 10. Seriously, it's that easy. – fleablood Feb 17 '18 at 18:07
1

I'm not going through the problem as I believe that you've done it yourself and you need to know how to find $6^{10} \pmod {215}$.

Firstly $215 = 5 \times 43$ which means there's a high chance of exploiting the Chinese Remainder Theorem but anyway, this is too trivial to use CRT.

(The following solution doesn't involve CRT; I just gave a reference of it)

Clearly, $6^{10} \equiv 1 \pmod {5}$. It's not a hard enough issue to see that $6^3 \equiv 1 \pmod {43} \implies 6\cdot(6^3)^3 \equiv 6 \cdot 1^3 \pmod {43}$.

And you're left with the system of equations namely : $$6^{10} \equiv 1 \equiv 6\pmod {5}$$ $$6^{10} \equiv 6 \pmod {43}$$

So, note that both $5$ and $43$ divides $6^{10}-6$ and since they're coprime, their product = $215$ also divides $6^{10}-6$ ensuring $6$ to be the desired remainder.

And if you want a faster method to solve, go for Wolfram Alpha. Just type out 6^10 mod 215 and you're done!

Finally, the remainder is $\boxed{6}$

  • "but anyway, this is too trivial to use CRT." ... but then... you use it? – fleablood Feb 16 '18 at 19:19
  • @fleablood No, I didn't use it. I just gave a reference of it. –  Feb 16 '18 at 19:20
  • Uh, noting that $6^{10} \equiv 1 \mod 5$ and $6^{10} \equiv 6 \mod 43 \implies 6^{10} \equiv 6 \mod 215$ isn't using the CRT?????? – fleablood Feb 16 '18 at 19:21
  • @fleablood If you interpret it that way then yes. But basically, I tried to convey that both $5$ and $43$ divides $6^{10}-6$ and since they're coprime, their product = 215 also divides $6^{10}-6$ –  Feb 16 '18 at 19:23
  • Maybe I should edit my answer and clarify what I mean. –  Feb 16 '18 at 19:23
  • No, I'm just nitpicking. It's clear what you mean. – fleablood Feb 16 '18 at 19:29