Saw this tweet from Matt Enlow yesterday:
I liked this problem both as an illustration of mathematical thinking and as a problem you can share with kids.
For mathematical thinking, the point is made really well in this interview with Julie Rehmeyer. The ~5 min part beginning around 31:30 about proving that 0 + 0 = 0 is what I’m thinking of specifically:
Julie Rehmeyer’s “Inspired by Math” interview
I had a similar feeling on seeing Matt’s problem – it wasn’t obvious to me why the Fibonacci numbers should have this property, but I had some ideas about how you’d prove that they did:
For sharing with kids, I like this problem because it is (i) accessible, but (ii) probably not as obvious how to solve it. I shared it with my son this morning and although we didn’t solve the problem it was very interesting to hear the ideas he had about how you might go about solving it:
I’m excited to finish up this problem with my son later this week and also excited to try out this problem with a larger group of kids sometime.
Mike's Math Page 
Well, if you look at triples (F_n, F_{n+1}, F_{n+2}) mod 72, there are only finitely many possibilities, so once it repeats you know you’ve seen all possibilities for F_n mod 72. This proves that this problem is a finite check (and gives a bound on how big the check is), though I’m hopeful that there’s a less laborious solution.
Wow, this is a great challenge to follow the additive chains activities we did a while ago.
indeed – your activity looks like a nice way to help kids make the jump from base 10 to base n.
I finally got around to checking that it’s not that laborious at all.
0,1,1,2,3,5,8,13,21,34,55,17,0,17,17,34,51,13,64,5,69,2,71,1,0,1,…
The only multiple of 9 there is 0. QED.
Actually, once you get to 0,17 you know it’s going to repeat from the beginning but x17, which doesn’t affect 8 or 9. So you could stop checking for multiples of 9 already at that point.
It’s not important that 17^2 = 1 mod 72, i.e. that the next time you see 0 you’re already back to 0,1.
In addition, the only multiples of 8 in that sequence are 0, 8, 64. Which tells you that the converse is almost true: if a Fibonacci number is a multiple of 8, then it’s either a multiple of 9 or 1 off.
Our follow up project is here:
https://mikesmathpage.wordpress.com/2016/03/01/following-up-on-matt-enlows-fibonacci-problem/
I thought this was a nice introduction to modular arithmetic and basic proof concepts for kids.
Dave Radcliffe on twitter also pointed out that there is a connection with a neat GCD formula for Fibonacci numbers:
GCD(Fib(n),Fib(m)) = Fib(GCD(n,m))