Divisibility by 7 is a Walk on a Graph, by David Wilson
My guest blogger is David Wilson, a fellow fan of sequences. It is a nice exercise to understand how this graph works. When you do, you will discover that you can use this graph to calculate the remainders of numbers modulo 7. Back to David Wilson:
I have attached a picture of a graph.
Write down a number n. Start at the small white node at the bottom of the graph. 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.
Nothing earth-shattering, but I was pleased that the graph was planar.
Felipe Pait:
Are the divisibility graphs for other primes planar too? Are they easy to construct?
11 August 2009, 10:19 amLeo:
The graph of divisibility by 13 looks non-planar to me.
11 August 2009, 12:34 pmJeff:
Has anyone done a systematic study of diviability graphs in terms of other graph metrics? Is this already a defined corner of mathematics?
12 August 2009, 10:10 amAndrei Zelevinsky:
Nice idea! For my taste though I would sacrifice planarity and make the “remainders mod 7 clock” divided into 7 hours, with arrows 0 to 0, 1 to 3, 2 to 6, 3 to 2, 4 to 5, 5 to 1, and 6 to 4. Then say given n=325, you start at 0, take 3 steps clockwise, follow an arrow, take 2 steps clockwise, follow an arrow, take 5 steps clockwise and land at the remainder of 325 modulo 7.
12 August 2009, 11:31 amJames:
According to this, then, 5 is evenly divisible by 7. FAIL!
12 August 2009, 11:50 amJames:
Actually, I’m wrong — I didn’t count the dot at the end of the line segment joining the front and back of the horizontal circle.
12 August 2009, 11:53 amSeth Troisi:
5 is not evenly divisible by 7 on this graph.
Andrei Zelevinsky. I also like the mod 7 clock. I have used it in math projects once or twice.
12 August 2009, 2:03 pmShawn:
‘According to this, then, 5 is evenly divisible by 7. FAIL!’
I get stuck in the state right above the epsilon transition (the point with the left black arrow and right white arrow) from the start if I use 5. To me that doesn’t appear to say 5 is by 7…. Ouch…
12 August 2009, 3:28 pmMatt Might:
It is possible to construct a finite-state machine which determines divisibility for any divisor n.
There are n states: “0 mod n”, …, “n-1 mod n”. 0 mod n is the accepting state.
If you’re in state “k mod n”, and the next digit is d, then you got to state “k*b + d mod n” where b is the base of your number system.
12 August 2009, 4:09 pmDavid Wilson:
Let G(b,m) be the graph for base b >= 2 and modulus m >= 1.
The black edges (the clock edge) forms a Hamiltonian cycle H. Every other edge is incident on nodes in H (since H includes all nodes). If we number the nodes like a clock, 0 through m-1, then call edges (x1,y1) and (x2,y2) with x1 < x2 < y1 10,edges (3,6),(4,8),(5,10) are pairwise incompatible. Two of these three edges must be on the same side of H,and hence cross,destroying planarity of G(b,m). So b = 2 => m m = 4, (1,b),(2,2b),(3,3b) are incompatible, so b >= 4 implies m <= 3b. For any base b, there are a finite number of moduli m for which G(b,m) is planar.
I’m working on a program.
12 August 2009, 11:41 pmDavid Wilson:
A chunk of my post must have gotten deleted because it looked like an html tag. Sigh.
12 August 2009, 11:44 pmDavid Wilson:
For 2 <= b = 4, m = 2b+2 is the largest planar modulus. It appears that all the divisors of 2b+2, 2b and b-1 are planar. Moduli 1,2,3,4,5 and 7 are planar for every m.
b = 2: m = 1 2 3 4 5 6 7
b = 3: m = 1 2 3 4 5 6 7 8 9 10
b = 4: m = 1 2 3 4 5 7 8 9 10
b = 5: m = 1 2 3 4 5 6 7 8 10 12
b = 6: m = 1 2 3 4 5 6 7 9 12 14
b = 7: m = 1 2 3 4 5 6 7 8 9 10 11 14 16
b = 8: m = 1 2 3 4 5 6 7 8 9 11 16 18
b = 9: m = 1 2 3 4 5 6 7 8 9 10 14 18 20
b = 10: m = 1 2 3 4 5 7 9 10 11 20 22
b = 11: m = 1 2 3 4 5 6 7 8 10 11 12 14 22 24
b = 12: m = 1 2 3 4 5 6 7 8 9 11 12 13 24 26
b = 13: m = 1 2 3 4 5 6 7 8 9 10 12 13 14 26 28
b = 14: m = 1 2 3 4 5 6 7 10 13 14 15 28 30
b = 15: m = 1 2 3 4 5 6 7 8 9 10 14 15 16 30 32
b = 16: m = 1 2 3 4 5 7 8 9 15 16 17 32 34
b = 17: m = 1 2 3 4 5 6 7 8 9 10 12 16 17 18 34 36
b = 18: m = 1 2 3 4 5 6 7 9 11 12 17 18 19 36 38
b = 19: m = 1 2 3 4 5 6 7 8 9 10 11 18 19 20 38 40
b = 20: m = 1 2 3 4 5 6 7 8 10 14 19 20 21 40 42
b = 21: m = 1 2 3 4 5 6 7 8 9 10 11 14 20 21 22 42 44
b = 22: m = 1 2 3 4 5 7 9 11 21 22 23 44 46
b = 23: m = 1 2 3 4 5 6 7 8 10 11 12 14 16 22 23 24 46 48
b = 24: m = 1 2 3 4 5 6 7 8 9 10 12 16 23 24 25 48 50
b = 25: m = 1 2 3 4 5 6 7 8 9 10 12 13 14 24 25 26 50 52
12 August 2009, 11:54 pmInteresting Information: Divisibility by 7 using a graph « Use Your Illusion:
[…] leave a response I found this off this Math blog: http://blog.tanyakhovanova.com/?p=159 […]
15 August 2009, 11:05 amDavid Wilson:
Empirically, it looks like the graph for base b and mod m is planar if one of the following is true:
b == -1, 0, or 1 (mod m)
m is even and b == m/2-1 or m/2 (mod m)
m = 5 and b == 2, 3 (mod m)
m = 7 and b == 2, 3, 4, 5 (mod m)
m = 8 and b == 5 (mod m)
m = 9 and b == 3, 4, 6, 7 (mod m)
m = 10 and b == 3, 7 (mod m)
m = 11 and b == 7, 8 (mod m)
m = 14 and b == 9, 11 (mod m)
Proving it would be tough.
19 August 2009, 7:28 amAnup Pandey:
Want comments on this that i have had with me for decades now, none of my mathematician friends that I told this about have been of any help so far - I would LOVE your feedback on this.
Divisibility Rule for 7
by Anup Pandey
Discovered - 1985
Take a number n
if n is divisible by 7 then truncate((n+10)/10) + 2*(10-mod(n/10)) is divisible by 7
example take n = 49 then
truncate(59/10) = 5
mod(n/10) = 9
so then, 10-9 = 1
then 2* 1 = 2
so we get 5 + 2 = 7 which is also divisble by 7
Another example -
n= 434
truncate (444/10) = 44
2* (10-mod(434/10)) = 2*6 = 12.
So 12 + 44 = 56, which is divisible by 7
24 August 2009, 12:30 pmEmre Yucel:
Let’s simplify this…
25 August 2009, 11:01 amif n is divisible by 7 then truncate((n+10)/10) + 2*(10-mod(n/10)) is divisible by 7
if n is divisible by 7 then mod(n/7) is 0
Wiskundemeisjes » Blog Archive » Deelbaarheid door 7:
[…] de rest van een getal is bij deling door 7. Maar het is leuker om dat zelf uit te zoeken. En kijk hier voor de interessante reacties op haar stukje. « […]
2 September 2009, 3:01 amVincent:
Dear Anup
I hope you still read this. Let’s write n = 10x + y, with y between 0 and 9.
then truncate(n + 10)/10 = x + 1
and 2*(10 - mod(n/10) = 20 - 2y
So what you want to show is that if n = 10x + y is divisible by 7, then so is x + 21 - 2y.
Let’s go. First we see that if n is divisible by 7 then so is 5n. 5n = 50x + 5y.
But since 49 is divisible by 7 this means that x + 5y is divisible by 7 as well. (*)
7y is certainly divisible by 7 so substracting 7y from some number which is divisible by 7 doesn’t change anything.
We conclude from (*) that x - 2y is divisible by 7. Now since 21 is 3*7 it follows that x + 21 - 2y is also divisible by 7 and this is what we wanted to show.
How did you find this rule?
2 September 2009, 4:06 amFunny Little Puzzle « NOAM GR!:
[…] One of my favorite math blogs is Tanya Khovanova’s. Every so often she’ll post a neat meathematical construction or puzzle. This one she posted last week I thought was pretty neat. I guess it counts as both a […]
14 October 2009, 10:10 pmK. C. Koh:
I have programmed the algorithm by C language. You can down load the C source from the below site.
http://blog.joins.com/media/folderlistslide.asp?uid=kckohkoh&folder=75&list_id=11200986
By this program, you can check a large number(up to 100 digits which can be extended by simply increasing the size of array variables in the source). I would like share my program if you keep to notify that its athority belongs to me.
29 November 2009, 11:26 am