Gears and rings…

Denys Fisher was a British engineer and maker of board games and other toys. In 1965 he invented the Spirograph toy. Some speculate that he was influenced by the designs of the artist, composer, and film animator John Whitney, whose opening sequence for Alfred Hitchcock’s 1958 film “Vertigo” is considered the first use of computer graphics in cinema. The Spirograph toy involves drawing with a pen guided by a gear with m teeth going around inside a ring or around a track or other gear with x teeth. The kind of design you get depends on how x relates to m.

Today Ken and I want to talk about a basic notion of mathematics and theory that is simple to define, very useful, and yet seems to be tough for some students to get.

The notion is:

Often mathematical ideas are not easy to trace: who defined multiplication first, or square roots, or any other basic notion? Often the notion is credited not to the person who invented it, but the one who first used it in some important way.

That is not the case for the notion of congruence. We know who defined it, when they defined it, and what they used it for. The “they” was the 21-year-old Carl Gauss, who in his famous 1798 Disquisitiones Arithmeticae introduced both the concept and the notation.

It is interesting that while Gauss selected a perfect notation for his brilliant notion, others were less excited. Adrien-Marie Legendre wanted to write

,

with the m implicit. Others suggested variations of

Gauss had nailed the right notion and it stuck—thankfully.

Gauss objected to Legendre’s double use; Charles Babbage also said it violated the doctrine of one notation for one thing. What all seem to have had in common was wanting to view it as a relation between two things, but it really involves three: m as well as x and y.

A common expression that something is complex to understand is that it has “gears within gears.” As embodied in Spirograph, congruence is exactly that. Can we make it as easy as a child’s toy?

Why So Hard To Learn?

The definition is, of course, that

if and only if divides .

I know most of you know this cold, but stay with us. We are not trying to advance your knowledge of this famous definition, but discuss why it is hard to learn. I think there are topics in math that are complex to state but can be learned without much difficulty. Yet this simple definition of Gauss is in my teaching experience not easy for many students to really get. The fundamental question is:

Why is the notion of congruence so difficult to understand?

At Tech I used to teach the beginning discrete math class for our majors. It covered all the usual stuff: basic number theory, graph theory, set theory, basic rules of logic, Galois cohomology, and recurrences. Actually we did not cover Galois anything, but I added that to see if you were reading. I often started with number theory, since the students—I thought—had seen numbers since grade school. But the concept of congruence always seemed hard to make register. Was it my poor teaching? Or was it something else?

A Theory

We have a modest theory on why congruence is tricky to learn. The main thesis is that it really is two important ideas that are thrown together. The problem is that the two ideas are not on equal footing. One is naturally high and abstract, the other so low one can easily “forget” it.

The first idea is that given an integer m there is the arithmetic modulo m. In many places on the web this is introduced as “clock arithmetic.” In the US this means that m = 12, while in Europe and elsewhere m = 24. But then it is explained how to add, subtract, and multiply numbers modulo m. Of course this is quite interesting, since this is essentially the study—in disguise—of finite commutative rings of a special type. The addition part is generated by the unit of the ring.

Gauss’s brilliant insight is that such simple objects had a deep and rich theory. The multiplicative structure of such a simple object is quite nontrivial. For example, there is the theorem that when the order—that is to say, the number of elements—is prime, then the nonzero elements form a cyclic group under multiplication. This is a deep theorem. Why should the 16 nonzero elements modulo 17 be cyclic? So are the 18 elements modulo 19, but Gauss found further properties that allow a regular 17-gon to be constructed by classical means and a regular 19-gon not. This verges into the theory of the Legendre symbol and quadratic reciprocity.

These and many other important theorems are available for the elements modulo m. This is a rich area, with many problems remaining open today. So the first hitch is that students must learn some slice of the basics of what is really a deep theory. Even just saying “commutative ring” might sound like saying “Galois cohomology.” What compounds the trouble, we believe, is that while the basic results are not terribly difficult, the motivation is unclear. Why are these objects so important? Today the best answer is these objects play a critical role in cryptography and coding theory and other aspects of theory.

If we stopped there, perhaps that would be enough. Perhaps it would be less confusing to our students. Maybe I will try that next time I have to teach this material. I could say:

Pick a natural number . Then define addition and multiplication on

as follows…

We would then prove that it had lots of nice properties and we could give some nice applications. RSA anyone?

The Second Difficulty

The key to the power of congruence is: it throws information away. If two integers x and y are equal, then for any m,

This means that congruence is in some sense a “forgetful functor.” This aspect underlies applications such as noted here:

Many problems in number theory reduce to the question of the solvability or unsolvability of some type of congruence. … In this connection, research into the question of the number of solutions of a congruence equation is of fundamental importance to number theory.

The sources, however, seem not to explain why this is true. The idea is simple but critical:

for any m that you choose. This means that we can reduce showing to showing that

is false for some m. This is one of the big ideas in mathematics. Often it is hard to show that x and y are not equal, yet it is much easier to show they are not congruent. This is a brilliant insight, and a surprising one.

Note this is quite counter-intuitive. You take x and y and throw away information about them, and then it becomes easier to handle them. It becomes easier to prove that they are different. Amazing. When you have some freedom to choose m or know a bound on x and y you can use the same idea to prove them equal. Or at least you can gain confidence in equality by sampling m randomly.

Here is a simple example. How can we show that can never equal (unless both x and y are zero)? First if they have a common factor we could divide it out without affecting the equation. That needs a pause for thought, but in fact we only need to visualize it when the factor is 3. Now we use the ‘forgetful’ trick and observe that if then

We’ve agreed that 3 cannot divide both x and y. If it divides neither we get which is impossible because . If 3 divides only x, then we get . But this implies that 3 divides y, which is again a contradiction. The same works if we start with 3 dividing only y. There is no way out. So .

How to Motivate?

Gauss seems to have thought the “forgetting” idea to be obvious beyond need of mention. At least I do not find any mention of it in my English edition of his book. Yet it strikes me both as a vital point and a connection that needs to be reinforced when teaching. It would be an interesting test of our hypothesis if emphasizing this simple “transfer principle” were shown to improve students’ results—or not.

The other difficulty remains problematic. David Mumford, who won a Fields Medal in 1974 for work in algebraic geometry and has recently started a blog on his website, co-wrote an obituary for Alexander Grothendieck with John Tate in the journal Nature. In his post on the editorial difficulties of explaining Grothendieck’s central notion of scheme to scientists in other fields, he wrote:

“To be honest, the central stumbling block for explaining schemes was the word ‘ring.’ … As for finite fields, in spite of John’s discomfort, I thought the numbers on a clock made a decent first exposure. OK, is not a field but what faster way to introduce finite rings than saying ‘a type of number that are added like the hours on a clock — 7 hours after 9 o’clock is not 16 o’clock, but 4 o’clock’?”

If the term ‘ring’ is a block for scientists then it needs special effort to convey the concept to students however it arises. Mumford says in his next paragraph:

“If math was introduced as connected to the rest of the world instead of being an isolated exercise, if it was shown to connect to money, to measuring the real world, to physics, chemistry and biology, to optimizing decisions and to writing computer code, fewer students would be turned off.”

Ken wonders whether reference to Spirograph and other cases of “gears within gears” can help here. In his novel Cryptonomicon, Neal Stephenson explained the role of congruence in breaking the Enigma code via an analogy to Alan Turing’s bicycle. Its rear wheel has one bent spoke and its chain has one vulnerable link. If they ever come together the bike will jam. The wheel’s sprocket has m teeth and the chain has x links. How frequently will this happen? Maybe never? This post emphasizes the idea of forgetting the total distance C that the chain has traveled and keeping only the congruence.

Open Problems

We use congruences all the time in computer theory. Are there other types of “throw information away” methods that we can also use?