Remainders

Leave a comment Go to comments

Find the smallest number that has a remainder of 1 when divided by 2, a remainder of 2 when divided by 3, a remainder of 3 when divided by 4, a remainder of 4 when divided by 5, a remainder of 5 when divided by 6, a remainder of 6 when divided by 7, a remainder of 7 when divided by 8, a remainder of 8 when divided by 9 and a remainder of 9 when divided by 10.

The brute-force method is not recommended, and neither is the technical out-of-the-box method (using the Chinese Remainder Theorem—see below).  Instead, by choosing the conditions wisely one at a a time, one is bound to find the solution much faster.  For instance:

  • The last condition (it has a remainder of 9 when divided by 10) tells us that the number actually ends in 9.  This makes unnecessary conditions one and four (it has a remainder of 1 when divided by 2, and it has a remainder of 4 when divided by 5).
  • It is obvious that the solution cannot have one single digit.  In order to disregard most two-digit numbers, we make use of the third condition (it has a remainder of 3 when divided by 4).  This means, in particular, that the last two digits must have a remainder of 3 when divided by four.  The only possibilities are therefore 19, 39, 59, 79 or 99.
  • Another quick check indicates that the solution cannot be a two-digit number.  We then use the seventh condition (it has a remainder of 7 when divided by 8) to rule out most three-digit endings: the last three-digits of the solution must have a remainder of 7 when divided by 8.

The application of these conditions have reduced significantly the number of possibilities.  It should be clear by now that the smallest such number will have at least four digits, and among those, it is fairly simple to choose the correct solution.  To aid the reader in that task, I present below a list of simple tests for divisibility:

  • Divisibility by 2: the last digit is even. Remainder: 0 if even, 1 if odd.
  • Divisibility by 3: The digital root of the number must be a multiple of 3.  The remainder is 0 for multiples of 3; otherwise, it is either 1 or 2.  The remainder of the number equals the remainder of its digital root.
  • Divisibility by 4: The last two digits are divisible by 4.  The remainder coincides with the remainder of the last two digits.
  • Divisibility by 5: The last digit is either 0 or 5.
  • Divisibility by 6: Divisible by 2 and 3 simultaneously.
  • Divisibility by 7: No easy test.
  • Divisibility by 8: The last three digits are divisible by 8.  The remainder coincides with the remainder of the last three digits.
  • Divisibility by 9: The digital root is 9.  The remainder is the same as the digital root.
  • Divisibility by 10: It ends in zero. The remainder coincides with the last digit.

 

Miscellaneous

The Chinese Remainder Theorem indicates us how to solve the following problem:

Let n_1, n_2, \dotsc, n_k be integers which are relatively prime in pairs: (n_i, n_j) = 1 for all i \neq j. For any a_1, a_2, \dotsc, a_k \in \mathbb{Z} there is a solution x \in \mathbb{Z} to the simultaneous congruences

\left\{ \begin{array}{c}x \equiv a_1 \text{ mod } n_1, \\ x \equiv a_2 \text{ mod } n_2, \\ \vdots \\ x \equiv a_k \text{ mod } n_k, \end{array} \right.

and the solution is unique \text{mod } n=n_1n_2 \dotsb n_k.

To compute such solution, we proceed as follows:

  1. Let m_j = n/m_j be the quotient of m by n_j, which is relatively prime to n_j by assumption.
  2. Let t_j be the inverse of m_j \text{ mod } n_j (these can be quickly found by the Euclidean Algorithm writing an_j + bm_j = (n_j, m_j) = 1, and taking t_j = b)
  3. A solution to the problem is then given by x = a_1 t_1 m_1 + \dotsb + a_k t_k m_k \text{ mod } n.

In the case of this puzzle, I would start by solving the partial remainder theorem for conditions one, two, four and six (the remainders by division over prime numbers), and then force the conditions of divisibility by ten, four, eight and nine (in that order), to get to the final answer.  As the reader can easily realize, the previous method reaches the solution without having to realize complicated computations.

  1. Silvio Moura Velho
    October 29, 2012 at 1:27 pm
    Reply

    Sometimes divisibility by 7 is referred as a difficult rule. I would like those who think so that visit my blogspot that shows since 2.005 the first real rule for divisibility by 7 that I created.

  1. No trackbacks yet.

Leave a comment