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

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 n∗10 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 N1∗10 mod 7.
3. We repeat step 1 to follow the black arrow N2 number of times. Now we are at N1∗10+N2 mod 7.
4. We follow step 2 again to arrive at N1∗100+N2∗10 mod 7.
5. Applying the same procedure until the last digit, we finally arrive at the node N1∗10m−1+N2∗10m−2+..+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.

Divisibility by 7 :-

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.