# divisibility by seven by “A walk in the graph”, Can you solve?

1,346.4K Views

It is pretty interesting. Not only can it tell us whether the number is divisible by 7 but also the exact remainder obtained if the number is divided by 7.

How this works is that each node is connected to a remainder by 7. That is each node has a unique number in [0..6] associated with it. And the rest is simple modular arithmetic.

To enumerate the associated numbers, the bottom-most node has 0 associated with it. From there, keep following the black arrows- you’ll obtain the node associated with the next number. As in the right-most node is associated with 1, the topmost with 2 and so on. You’ll notice that the leftmost node is associated with 6 which in turn leads to 0.

You should also notice that the white arrows lead up from nodes n mod 7 to nodes n10 mod 7. This is important.

Now let us consider a number N with digits N1,N2...Nm with Nm being the unit digit.

We begin applying the given algorithm:

1. We follow the black arrow N1 number of times and arrive at the node N1 mod 7.
2. Next we follow the white arrow to arrive at the node N110 mod 7.
3. We repeat step 1 to follow the black arrow N2 number of times. Now we are at N110+N2 mod 7.
4. We follow step 2 again to arrive at N1100+N210 mod 7.
5. Applying the same procedure until the last digit, we finally arrive at the node N110m1+N210m2+..+Nm mod 7 which equals N mod 7. If we are at the bottommost node, then we conclude that N mod 7=0 and hence proving the divisibility of N by 7.

If anything is unclear, feel free to leave comments.

Found this cool test for divisibility by 7 on Tanya’s website. Read about how to use it here, but basically you follow that diagram a certain way.

and yes the graph is planar.
1. Write down a number n.
2. Start at the small white node at the bottom of the graph.
3. For each digit d in n, follow d black arrows in a succession, and as you move from one digit to the next, follow 1 white arrow.

For example, if n = 325, follow 3 black arrows, then 1 white arrow, then 2 black arrows, then 1 white arrow, and finally 5 black arrows.

If you end up back at the white node, n is divisible by 7.