What is a congruence equation for this problem

Question

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?

Answer 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$.

Answer 2

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}$