[OlymPri20150527NTSD] Sudoku with Modular Arithmetic?

Question

Introduction

     This is a pretty nasty-looking challenge.  It is like Sudoku, but only worse.  You probably cannot avoid some degree of trial-and-error (or [H07] guess and check).  There is a solution posted somewhere, but it is very long and chases many dead-ends before arriving at the solution.

     So how do we avoid making so many wild guesses?  We do so by making good use of number theory, which includes modular arithmetic.  In what follows, I am going to use the theory and notations as in my article (“Divisibility Tests for 7 and other digits”).  Please read the article to remind yourself of the various divisibility tests.

Solution

     It is easy to see that  j = 0. 

     Since abcde ¸ 5,  e Î {0, 5}.  But  0  is already taken, so  e = 5.

     Since divisibility is transitive (x ¸ y  and  y ¸ z  Þ  x ¸ z),  anything divisible by  4,  6  and  8  is also divisible by 2.  So  b, d, f, h  are all the even digits  2, 4, 6, 8  in some order, and  a, c, g, i  are the odd digits  1, 3, 7, 9  in some order.  From the divisibility tests for  3,  6  and  9,

     a+b+c º 0 (mod 3)

     a+b+c+d+e+f º 0 (mod 6)               Þ   a+b+c+d+e+f º 0 (mod 3)

     a+b+c+d+e+f+g+h+i º 0 (mod 9)   Þ   a+b+c+d+e+f+g+h+i º 0 (mod 3)

we get

     a+b+c º d+e+f º g+h+i º 0 (mod 3)

To narrow down the search space, we always test the group of digits that contain the most clues and the least unknowns (if possible).  Currently, this seems to be the middle group d5f.

     Using modulo 3,  d+5+f º 0   Þ   d+f º 1   Þ   d+f = 7, 10, 13  (because  2+4 < d+f < 6+8)

Since  d  and  f  are even digits, we can cross out  7  and  13.  So {d, f} = {6, 4}.

     abcd ¸ 4   Þ   cd ¸ 4   Þ   10c + d º 2c + d º 0   (mod 4)

If  d = 4,  then  2c º 0   (mod 4)   Þ   c º 0   (mod 2).  Not possible, as  c  is odd.

Now we know  d = 6  and  f = 4.  The number is  abc654ghi0,  and  {b, h} = {2, 8}.

Can  h = 8?  If so, we would have  4g8 º 4´100+g´10+8 º 2g  º  0 (mod 8).  g  º  0 (mod 4) 

g ¸ 4 ¸ 2.  But this is not possible, since  g  is an odd number.  Hence  know  h = 2  and  b = 8.  The number is  a8c654g2i0.  Now

4g2 ¸ 8   Þ   4´100+g´10+2 º 2g+2 º 0 (mod 8)   Þ   g+1 º 0 (mod 4)   Þ   g º -1 (mod 4)

   Þ   g Î {3, 7}.

If  g = 3, then working in mod 7, we have  a8c6 º 543,  and then

     Þ   a´1000+8´100+c´10+6 º 5´100+4´10+3

     Þ                  -a+8´2+c´3+6 º 5´2+4´3+3

     Þ                          3c – a + 1 º 4

     Þ                        a – 3(c – 1) º 0 (mod 7)

Note that  a  is an odd digit  and   c  is odd,  c – 1  is even,  3(c – 1)  is even and so  a – 3(c – 1)  is odd.  a – 3(c – 1) ¹ 0  because 0 is even.  Since  1 < a < 9,  a – 3(c – 1) = 7.  We need  a = 7  and  c = 1.  This would mean  i = 9.  But   g+h+i  º 3+2+9 º 2 (mod 3).  It is supposed to be 0 (mod 3).  So  g ¹ 3  i.e.  g = 7.  The number is  a8c65472i0.

Going back to mod 7,     a8c6 º 547

                               3c – a + 1 º 1

                                            a  º 3c

(a, c) = (3, 1) or (9, 3).  But if  (a, c) = (9, 3),  i = 1.  g+h+i  º 7+2+1 º 1 (mod 3), which is incorrect.  So we must have  a = 3 and   c = 1.  The remaining digit is   i = 9. 

The mystery number is 3816547290.  Bingo!

Heuristics Used

H03. Make a systematic list

H04. Look for pattern(s)

H05. Work backwards

H07. Use guess and check

H08. Make suppositions

H09. Restate the problem in another way

H10. Simplify the problem

H11. Solve part of the problem

H13* Use Equation / write a Mathematical Sentence

Hxx*  At each step, try to attack the part that has most clues and the least unknowns.

Suitable Levels

* Primary School Mathematics

* anyone game for a challenge requiring modular arithmetic

[NumTh Expository] Divisibility Tests for 7 and other digits

Introduction

     Let  n = ...ABCDEFG = ... + A´10⁶ + B´10⁵ + C´10⁴ + D´10³ + E´10² + F´10 + G. 

I invent the notation  ‘n ¸ d’  to mean  “n  is divisible by  d”  (as integers).  For a definition

n ¸ d   Û   d | n   Û   n = kd  for some integer  k

Many of you may have heard of the following divisibility tests:-

n ¸ 1   is always true   n ¸ 2   Û   the last digit  G ¸ 2   Û   the last digit  G Î {0, 2, 4, 6, 8}   n ¸ 3   Û   the sum of digits  ... A+B+C+D+E+F +G ¸ 3   n ¸ 4   Û   the last digits  FG ¸ 4   n ¸ 5   Û   the last digit  G ¸ 5   Û   the last digit  G Î {0, 5}   n ¸ 6   Û   n ¸ 2  and  n ¸ 3  (see above)   n ¸ 8   Û   the last digits  EFG ¸ 8   n ¸ 9   Û   the sum of digits  ... A+B+C+D+E+F+G ¸ 9 n ¸ 10   Û   the last digit  G = 0

What about divisibility by 7?

Modulo Arithmetic

     Divisibility tests are all based on modular arithmetic (a.k.a. clock arithmetic), as part of number theory.  This arithmetic was developed initally by a very clever mathematician

called Carl Friedrich Gauss.  The key idea is that numbers can be grouped into separate classes.  For example, when considering division by  3,  we can split the integers into three equivalence classes called residue classes

     [0] = { ..., -3, 0, 3, 6,   9, 12, ... }

     [1] = { ..., -2, 1, 4, 7, 10, 13, ... }

     [2] = { ..., -1, 2, 5, 8, 11, 14, ... }

The members of each class have the same remainder when divided by  3.  For example 

     10 ¸ 3 = 3r1,  7 ¸ 3 = 2r1,  4 ¸ 3 = 1r1  (all the remainders are equal to 1).

So  10, 7, 4, 1 ... etc are all members of the class  [1]  represented by  1.  Members of the same class are called congruent.  For example  10 º 4 (mod 3),  read as “10 is congruent to  4  modulo 3” and it means  10  and  4  have the same remainder when divided by  3.

a º b (mod m)   Û   (a – b) ¸ m   Û   a = b + km  for some integer  k

As you know,  “a ¸ m  gives a remainder of zero”  means  “a  is divisible by  m”.  Hence

a º 0 (mod m)   Û   a ¸ m

Congruency (for a given modulo m) is a type of equivalence relation.  We have these laws

Reflexivity:   For every integer a,  a º a Symmetry:    If  a º b,  then  b º a. Transitivity: If  a º b  and  b º c,  then  a º c.

These properties are similar to ‘=’.  We also have some very neat arithmetical laws.

Suppose  a º b (mod m)  and  c º d (mod m).  Then      a + c º b + d  (mod m)      a – c º b – d  (mod m)          ac º bd      (mod m)

For a given number  n = ...ABCDEFG,  we can write  n = 1000x + y   where  x = ...ABCD,  y = EFG.  With the above laws, modular arithmetic helps simplify calculations and provide powerful insights.  For example, in modulo 8,

         10 º 2,  100 º 10² º 2² º 4,  1000 º 10 ´ 10²  º 2 ´ 4 º 0.  Hence

         n = 1000x + y  º  0×x + y  º  y.

This explains the divisibility test by  8:  To see if a number is divisible by  8, we just need to look at the last  3  digits  y = EFG.

Test for divisibility by 7

     Using modulo 7,  10 º 3,  100 º 3² º 2,  1000 º 3 ´ 2 º 6 º -1.

     n = 1000x + y º  -1×x + y º  y – x.  Thus

     n ¸ 7   Û   n º y – x º 0   Û   x º y   Û    x – y ¸ 7.  We have the rule

n ¸ 7   Û   ...ABCD º EFG (mod 7)

This means that a number is divisible  7  if (and only if) after breaking off the last three digits, both resulting pieces have the same remainder when divided by  7.

Example 1

       For 12 516:  12 º 5  and  516 º 5 (mod 7).  So  12 516 ¸ 7.

Example 2

       For 654 321:  654 º 3  and  321 º 6 (mod 7).  So  654 321 not ¸ 7.

Example 3

       For 1 494 787:  787 º 3 º 1494 (mod 7).  So  1 494 787 ¸ 7.

       Alternatively, 1 494 – 787 = 707 ¸ 7.  So  1 494 787 ¸ 7.

Works like magic, doesn’t it?