Skip to main content
Engineering LibreTexts

0.2: Modular Arithmetic

  • Page ID
    7447
  • \( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)

    We write the set of integers as: \[\mathbb{Z} \stackrel{\text { def }}{=}\{\ldots,-2,-1,0,1,2, \ldots\}\notag\] and the set of natural numbers (nonnegative integers) as: \[\mathbb{N} \stackrel{\text { def }}{=}\{0,1,2, \ldots\} .\notag\] Note that 0 is considered a natural number.

    Definition 0.1

    For \(x, n \in \mathbb{Z}\), we say that \(n\) divides \(x\) (or \(x\) is a multiple of \(n\) ), and write \(n \mid x\), if there exists an integer \(k\) such that \(x=k n\).

    Remember that the definitions apply to both positive and negative numbers (and to zero). We generally only care about this definition in the case where \(n\) is positive, but it is common to consider both positive and negative values of \(x\).

    Example

    \(7\) divides \(84\) because we can write \(84=12 \cdot 7\).

    \(7\)divides \(0\) because we can write \(0=0 \cdot 7\).

    \(7\)divides \(-77\) because we can write \(-77=(-11) \cdot 7\).

    \(-7\) divides \(42\) because we can write \(42=(-6) \cdot(-7)\)

    1 divides every integer (so does \(-1\) ). The only integer that 0 divides is itself.

    Definition 0.2 (% operator)

    Let \(n\) be a positive integer, and let \(a\) be any integer. The expression \(a\%n\) (usually read as " \(a\) mod\(n ")\) represents the remainder after dividing \(a\) by \(n\). More formally, \(a \% n\) is the unique \(r \in\{0, \ldots, n-1\}\) such that \(n \mid(a-r).^{1}\)

    Pay special attention to the fact that \(a \% n\) is always a nonnegative number, even if \(a\) is negative. A good way to remember how this works is:

    1.jpg
    Example

    \(21 \% 7=0\) because \(21=3 \cdot 7+\underline{0}\).

    \(20 \% 7=6\) because \(20=2 \cdot 7+\underline{6}\).

    \(-20 \% 7=1\) because \(-20=(-3) \cdot 7+\underline{1} \cdot(-20\) is one more than a multiple of 7.)

    \(-1 \% 7=6\) because \(-1=(-1) \cdot 7+\underline{6}\).

    Unfortunately, some programming languages define \(\%\) for negative numbers as \((-a) \%\) \(n=-(a \% n)\), so they would define \(-20 \% 7\) to be \(-(20 \% 7)=-6\). This is madness, and it’s about time we stood up to these programming language designers and smashed them over the head with some mathematical truth! For now, if you are using some programming environment to play around with the concepts in the class, be sure to check whether it defines % in the correct way.

    Definition 0.3 \((\mathbb{Z}_{n})\)

    For positive \(n\), we write \(\mathbb{Z}_{n} \stackrel{\text { def }}{=}\{0, \ldots, n-1\}\) to denote the set of integers modulo \(n\). These \(\left(\mathbb{Z}_{n}\right)\) are the possible remainders one obtains by dividing by \(n^{2}\)

    Definition 0.4 \((\equiv_{n})\)

    For positive \(n\), we say that integers a and \(b\) are congruent modulo \(n\), and write \(a \equiv_{n} b\), if \(n \mid(a-b)\). An alternative definition is that \(a \equiv_{n} b\) if and only if \(a \% n=b \% n\).

    You’ll be in a better position to succeed in this class if you can understand the (subtle) distinction between \(a \equiv_{n} b\) and \(a=b \% n\) :

    \(a \equiv_{n} b\): In this expression, \(a\) and \(b\) can be integers of any size, and any sign. The left and right side have a certain relationship modulo \(n\).

    \(a=b \% n\): This expression says that two integers are equal. The "=" rather than "झ" is your clue that the expression refers to equality over the integers. " \(b \% n\) " on the right-hand side is an operation performed on two integers that returns an integer result. The result of \(b \% n\) is an integer in the range \(\{0, \ldots, n-1\}\).

    Example

    \(99 \equiv_{10} 19 "\) is true. Applying the definition, you can see that 10 divides \(99-19\).

    On the other hand, "99 \(=19 \% 10 "\) is false. The right-hand side evaluates to the integer 9 , but 99 and 9 are different integers.

    In short, expressions like \(a \equiv_{n} b\) make sense for any \(a\), \(b\) (including negative!), but expressions like \(a = b%n\) make sense only if \(a\in \mathbb{Z}_{n}\).

    Most other textbooks will use notation " \(a \equiv b(\bmod n)\) " instead of " \(a \equiv_{n} b\)." I dislike this notation because " \((\bmod n)\) " is easily mistaken for an operation or action that only affects the right-hand side, when in reality it is like an adverb that modifies the entire expression \(a \equiv b\). Even though \(\equiv_{n}\) is a bit weird, I think the weirdness is worth it.

    If \(d \mid x\) and \(d \mid y\), then \(d\) is a common divisor of \(x\) and \(y\). The largest possible such \(d\) is called the greatest common divisor (GCD), denoted \(\operatorname{gcd}(x, y)\). If \(\operatorname{gcd}(x, y)=1\), then we say that \(x\) and \(y\) are relatively prime. The oldest "algorithm" is the recursive process that Euclid described for computing GCDs (ca. \(300 \mathrm{BCE})\):

    2.jpg

    Tips & Tricks

    You may often be faced with some complicated expression and asked to find the value of that expression \(\bmod n\). This usually means: find the unique value in \(\mathbb{Z}_{n}\) that is congruent to the result. The straightforward way to do this is to first compute the result over the integers, and then reduce the answer \(\bmod n\) (i.e., with the \(\% n\) operator).

    While this approach gives the correct answer (and is a good anchor for your understanding), it’s usually advisable to simplify intermediate values mod \(n\). Doing so will result in the same answer, but will usually be easier or faster to compute:

    Example

    We can evaluate the expression \(6 \cdot 7 \cdot 8 \cdot 9 \cdot 10 \% 11\) without ever calculating that product over the integers, by using the following reasoning:

    \[\begin{aligned} 6 \cdot 7 \cdot 8 \cdot 9 \cdot 10 &=(42) \cdot 8 \cdot 9 \cdot 10 \\ & \equiv_{11} 9 \cdot 8 \cdot 9 \cdot 10 \\ &=(72) \cdot 9 \cdot 10 \\ & \equiv_{11} 6 \cdot 9 \cdot 10 \\ &=(54) \cdot 10 \\ & \equiv_{11} 10 \cdot 10 \\ &=100 \\ & \equiv_{11} 1 \end{aligned}\]

    In the steps that only work \(\bmod 11\), we write " \(\equiv_{11} "\). We can write "=" when the step holds over the integers, although it wouldn’t be wrong to write " \(\equiv_{11}\) " in those cases too. If wo expressions represent the same integer, then they surely represent values that are congruent mod \(11.\)

    My advice is to simplify intermediate values mod \(n\), but "simplify" doesn’t always mean "reduce mod \(n\) with the % \(n\) operation." Sometimes an expression can by "simplified" by substituting a value with something congruent, but not in the range \(\{0, \ldots, n-1\}\) :

    Example

    I can compute \(7^{500} \% 8\) in my head, by noticing that \(7 \equiv_{8}-1\) and simplifying thusly: \[7^{500} \equiv_{8}(-1)^{500}=1 .\notag\] Similarly, I can compute \(89^{2} \% 99\) in my head, although I have not memorized the integer \(89^{2}\). All I need to do is notice that \(89 \equiv_{99}-10\) and compute this way: \[89^{2} \equiv_{99}(-10)^{2}=100 \equiv_{99} 1\notag\] You can compute either of these examples the "hard way" to verify that these shortcuts lead to the correct answer.

    Since addition, subtraction, and multiplication are defined over the integers (i.e., adding/subtracting/multiplying integers always results in an integer), these kinds of tricks can be helpful.

    On the other hand, dividing integers doesn’t always result in an integer. Does it make sense to use division when working \(\bmod n\), where the result always has to lie in \(\mathbb{Z}_{n}\)? We will answer this question later in the book.


    \({ }^{1}\) The fact that only one value of \(r\) has this property is a standard fact proven in most introductory courses on discrete math.

    \({ }^{2}\) Mathematicians may recoil at this definition in two ways: (1) the fact that we call it \(\mathbb{Z}_{n}\) and not \(\mathbb{Z} /(n \mathbb{Z})\); and (2) the fact that we say that this set contains integers rather than congruence classes of integers. If you appreciate the distinction about congruence classes, then you will easily be able to mentally translate from the style in this book; and if you don’t appreciate the distinction, there should not be any case where it makes a difference. In short, expressions like \(a \equiv_{n} b\) make sense for any \(a, b\) (including negative!), but expressions like \(a=b \% n\) make sense only if \(a \in \mathbb{Z}_{n}\).


    This page titled 0.2: Modular Arithmetic is shared under a CC BY-NC-SA 4.0 license and was authored, remixed, and/or curated by Mike Rosulek (Open Oregon State) via source content that was edited to the style and standards of the LibreTexts platform; a detailed edit history is available upon request.

    • Was this article helpful?