Modular Arithmetic

Definition

Modular arithmetic is a system of arithmetic for integers, which considers the remainder. In modular arithmetic, numbers “wrap around” upon reaching a given fixed quantity (this given quantity is known as the modulus) to leave a remainder. Modular arithmetic is often tied to prime numbers, for instance, in Wilson’s theorem, Lucas’s theorem, and Hensel’s lemma, and generally appears in fields like cryptography, computer science, and computer algebra.

An intuitive usage of modular arithmetic is with a 12-hour clock. If it is 10:00 now, then in 5 hours the clock will show 3:00 instead of 15:00. 3 is the remainder of 15 with a modulus of 12.

A number x mod N is the equivalent of asking for the remainder of x when divided by N. Two integers a and b are said to be congruent (or in the same equivalence class) modulo N if they have the same remainder upon division by N. In such a case, we say that a ≡ b ( mod N ).¹

Who

You may never have heard of modular arithmetic, but you use it every day without the slightest difficulty. In this system, numbers wrap around when they reach a certain size called the modulus; it is the arithmetic of remainders. When reckoning hours, we count up to 12 and start again from one. Thus, four hours after 9 o’clock it is 1 o’clock. Numbers that differ by a multiple of the modulus 12 are said to be congruent modulo 12.

A similar situation arises for the days of the week, which are computed modulo seven. Suppose today is Thursday. What weekday will it be 1,000 days from today? We don’t have to count through the thousand days, just calculate the remainder when 1,000 is divided by seven, which is six. Then the weekday 1,000 days from today will be the same as in six days, a Wednesday.

It is much the same for other time measurements. With 52 weeks in a year, the week number is reset to 1 at the beginning of each year, so it is confined to the range 1 to 52. Likewise, for the months, we use modulo 12 arithmetic.²

---

I have mostly used modular arithmetic when I was programming in ColdFusion, PHP and C#, and mostly dealing with the calculation of dates, e.g., as leap years. You always need to know when February has 29 nine days as the nursey rhyme “Thirty Days Hath September” states:

Thirty days hath September,
April, June and November;
All the rest have thirty-one,
Excepting February alone.
Which only has but twenty-eight days clear
And twenty-nine in each leap year.

Leap Year

Check if the number is evenly divisible by 400 to confirm a leap year. If a year is divisible by 100, but not 400, then it is not a leap year. If a year is divisible by both 100 and 400, then it is a leap year.

For example, 1900 is evenly divisible by 100, but not 400 since it gives you a result of 4.75. This means that 1900 is not a leap year. On the other hand, 2000 is evenly divisible by 100 and 400, since it gives you a result of 5. That means that the year 2000 is a leap year.³

Here is an example of code used to calculate whether a given year is a leap year.

function isLeapYear (year):
    if (( year modulo 4 is 0 ) and ( year modulo 100 is not 0 ))
        or ( year modulo 400 is 0 ) then true
    else false

There are many more uses for modular arithmetic

What

Note what the Institute for Advanced Study website has to say about modular arithmetic:

For almost all its history, the study of modular arithmetic has been driven purely by its inherent beauty and by human curiosity. But in one of those strange pieces of serendipity which often characterize the advance of human knowledge, in the last half century modular arithmetic has found important applications in the “real world.” Today, the theory of modular arithmetic (e.g., Reed-Solomon error correcting codes) is the basis for the way DVDs store or satellites transmit large amounts of data without corrupting it. Moreover, the cryptographic codes which keep, for example, our banking transactions secure are also closely connected with the theory of modular arithmetic.”⁴

Why

Modular arithmetic is used extensively in pure mathematics, where it is a cornerstone of number theory. But it also has many practical applications. It is used to calculate checksums for international standard book numbers (ISBNs) and bank identifiers (Iban numbers) and to spot errors in them.

Modular arithmetic also underlies public key cryptography systems, which are vital for modern commerce. It is also widely used in computer science. Finally, in music theory, modulo 12 arithmetic is used to analyse the 12-tone equal temperament system, when notes separated by an octave of 12 semi-tones are treated as equivalent.²

See Theoretical Knowledge Vs Practical Application.

How

Many of the References and Additional Reading websites and Videos will assist you with modular arithmetic.

As some professors say: “It is intuitively obvious to even the most casual observer.“

References

¹ “Modular Arithmetic | Brilliant Math & Science Wiki”. 2022. brilliant.org. https://brilliant.org/wiki/modular-arithmetic/.

² “Modular arithmetic: you may not know it but you use it every day”. 2022. The Irish Times. https://www.irishtimes.com/news/science/modular-arithmetic-you-may-not-know-it-but-you-use-it-every-day-1.3268649.

³ “How To Calculate Leap Years: 7 Steps (With Pictures) – Wikihow”. 2022. wikihow.com. https://www.wikihow.com/Calculate-Leap-Years.

⁴ “Modular Arithmetic: Driven By Inherent Beauty And Human Curiosity”. 2012. Institute For Advanced Study. https://www.ias.edu/ideas/2012/taylor-modular-arithmetic.

Additional Reading

“Fun With Modular Arithmetic – BetterExplained”. 2022. betterexplained.com. https://betterexplained.com/articles/fun-with-modular-arithmetic/.

“Leap Years”. 2022. Mathsisfun.Com. https://www.mathsisfun.com/leap-years.html.

“What Are Some Well-Known Uses Of Modular Arithmetic?”. 2022. Quora. https://www.quora.com/What-are-some-well-known-uses-of-modular-arithmetic.

“What Is Modular Arithmetic, And Are There Any Real World Uses?”. 2022. Quora. https://www.quora.com/What-is-modular-arithmetic-and-are-there-any-real-world-uses.

“What Is Modular Arithmetic? (Article) | Khan Academy”. 2022. Khan Academy. https://www.khanacademy.org/computing/computer-science/cryptography/modarithmetic/a/what-is-modular-arithmetic.

“Why Is Modular Arithmetic Useful?”. 2022. Quora. https://www.quora.com/Why-is-modular-arithmetic-useful.

Videos