Where Do Those Undergraduate Divisibility Problems Come From? | Chris Grossack's Blog

Oftentimes in your “intro to proofs” class or your first “discrete math” class or something similar, you’ll be shown problems of the form “prove that for $n^6 + n^3 + 2n^2 + 2n$ is a multiple of $6$ for every $n$”… But where do these problems come from? And have you ever stopped to think how magical this is? If I gave you some random polynomial in $n$ and asked you if it always output multiples of $6$, the answer would almost always be “no”! So if you really needed to come up with an example of this phenomenon, how would you do it? In this blog post, we give one approach!

I want to give some sort of attribution for this, since I remember reading about this exact topic… like a long time ago. Maybe 6 or 7 years ago? I’m sure that I saved the relevant article1 in my zotero, but I can’t find it for the life of me! Regardless, I want to emphasize that the whole idea for this topic (using Pólya-Redfield counting to build these divisibility problems) is not mine.

I’ve wanted to write a post on Pólya-Redfield counting for years now, since it was a pet topic of mine as an undergrad, but I think I was always planning too big a scope. This is a very bite-sized problem, and I won’t go into the theory very deeply, so I think it should make for a blog post I can finish in a day2.

Leave a Comment