Skip to main content
Engineering LibreTexts

13.1: “Dividing” Mod n

  • Page ID
    7397
  • \( \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}}\)

    to-do

    I'm considering moving some of this material to Chapter 3 (secret sharing) - enough to understand that every nonzero element has a multiplicative inverses modulo a prime (totients, etc can stay here). That way, I don’t have to say "trust me, this can be made to work" when describing Lagrange interpolation over a prime field, and students can play around with secret sharing using Sage. Also, students will see that there is "serious math" in the course already in chapter 3 so they don’t get blindsided as we transition into public-key crypto. (Not to mention, this chapter is too long.)

    Please review the material from Section \(0.2\), to make sure your understanding of basic modular arithmetic is fresh. You should be comfortable with the definitions of \(\mathbb{Z}_{n}\), congruence \(\left(\equiv_{n}\right)\), the modulus operator \((\%)\), and how to do addition, multiplication, and subtraction \(\bmod n\).

    Note that we haven’t mentioned division mod \(n\). Does it even make sense to talk about division \(\bmod n ?\)

    Example

    Consider the following facts which hold mod 15:

    fig-ch01_patchfile_01.jpg
    Figure \(\PageIndex{1}\): Copy and Paste Caption here. (Copyright; author via source)

    Now imagine replacing ".8" with " \(\div 2 "\) in each of these examples:

    fig-ch01_patchfile_01.jpg
    Figure \(\PageIndex{1}\): Copy and Paste Caption here. (Copyright; author via source)

    Everything still makes sense! Somehow, multiplying by \(8\) mod \(15\) seems to be the same thing as “dividing by \(2\)” mod \(15\).

    The previous examples all used \(x\cdot 8\left ( x\div 2 \right )\) where \(x\) was an even number. What happens when \(x\) is an odd number?

    \[3\cdot 8\equiv _{15}9\Leftrightarrow "3\div 2\equiv _{15}9"??\]

    This might seem non-sensical, but if we make the substitutions \(3\equiv _{15}-12\) and \(9\equiv _{15}-6\), then we do indeed get something that makes sense:

    \[-12\cdot 8\equiv _{15}-6\Leftrightarrow -12\div 2\equiv _{15}-6\]

    This example shows that there is surely some interesting relationship among the numbers 2, 8, and 15. It seems reasonable to interpret “multiplication by 8” as “division by 2” when working mod 15.

    Is there a way we can do something similar for “division by 3” mod 15? Can we find some \(y\) where “multiplication by \(y\) mod 15” has the same behavior as “division by 3 mod 15?” In particular, we would seek a value \(y\) that satises \(3\cdot y\equiv _{15}1\), but you can check for yourself that no such value of \(y\) exists.

    Why can we “divide by 2” mod 15 but we apparently cannot “divide by 3” mod 15? We will explore this question in the remainder of this section.

    Multiplicative Inverses

    We usually don’t directly use the terminology of “division” with modular arithmetic. Instead of saying “division by 2”, we say “multiplication by \(2^{-1}\)”, where \(2^{-1}\) is just another name for 8.

    Definition \(13.1\) (\(x^{−1}\) mod \(n\))

    The multiplicative inverse of \(x\) mod \(n\) is the integer \(y\) that satisfies \(x\cdot y\equiv _{n}1\) (if such a number exists). We usually refer to the multiplicative inverse of \(x\) as “\(x^{-1}\).”

    Example

    Continuing to work mod \(15\), we have:

    • \(4^{-1}\equiv _{15}4 \text{ since } 4\cdot 4= 16\equiv _{15}1\). Hence \(4\) is its own multiplicative inverse! You can also understand this as: \[4^{-1}=\left ( 2^{2} \right )^{-1}=\left ( 2^{-1} \right )^{2}\equiv _{15}4\]
    • \(7^{-1}\equiv _{15}1 \text{ since } 7\cdot 13= 91\equiv _{15}1\).

    We are interested in which numbers have a multiplicative inverse mod \(n\).

    Definition 13.2 \(\mathbb{Z}_{n}^{*} \)

    The multiplicative group\({ }^{2}\) modulo \(n\) is defined as: 

    \[\mathbb{Z}_{n}^{*} = \left \{ x\in \mathbb{Z}_{n}\big| x\text{ has a multiplicative inverse mod }n \right \}\]

    For example, we have seen that \(\mathbb{Z}_{n}^{*}\) contains the numbers 2, 4, and 7 (and perhaps others), but it doesn’t contain the number 3 since 3 does not have a multiplicative inverse.

    So which numbers have a multiplicative inverse mod \(n\), in general? (Which numbers belong to \(\mathbb{Z}_{*} n\) ?) The answer is quite simple:

    Theorem \(13.3\)

    \(x\) has a multiplicative inverse \(\bmod n\) if and only if gcd \((x, n)=1 .\) In other words, \(\mathbb{Z}_{n}^{*}=\{x \in\) \(\left.\mathbb{Z}_{n} \mid \operatorname{gcd}(x, n)=1\right\}\)

    We prove the theorem using another fact from abstract algebra which is often useful:

    Theorem \(13.4\)

    For all integers \(x\) and \(y\), there exist integers a and buch that ax \(+b y=\operatorname{gcd}(x, y)\). In fact, (Bezout’s Theorem) \(\operatorname{gcd}(x, y)\) is the smallest positive integer that can be written as an integral linear combination of \(x\) and \(y\)

    We won’t prove Bezout’s theorem, but we will show how it is used to prove Theorem \(13.3\) :

    Proof (of Theorem 13.3)

    \((\Leftarrow)\) Suppose \(\operatorname{gcd}(x, n)=1\). We will show that \(x\) has a multiplicative inverse mod \(n\). From Bezout’s theorem, there exist integers \(a, b\) satisfying \(a x+b n=1\). By reducing both sides of this equation modulo \(n\), we have \[1=a x+b n \equiv_{n} a x+b \cdot 0=a x .\] Thus the integer \(a\) that falls out of Bezout’s theorem is the multiplicative inverse of \(x\) modulo \(n\).

    \((\Rightarrow)\) Suppose \(x\) has a multiplicative inverse \(\bmod n\), so \(x x^{-1} \equiv_{n} 1\). We need to show that \(\operatorname{gcd}(x, n)=1\). From the definition of \(\equiv_{n}\), we know that \(n\) divides \(x x^{-1}-1\), so we can write \(x x^{-1}-1=k n\) (as an expression over the integers) for some integer \(k\). Rearranging, we have \(x x^{-1}-k n=1\). Since we can write 1 as an integral linear combination of \(x\) and \(n\), Bezout’s theorem says that we must have \(\operatorname{gcd}(x, n)=1\).

    Example

    \(\mathbb{Z}_{15}=\{0,1, \ldots, 14\}\), and to obtain \(\mathbb{Z}_{15}^{*}\) we exclude any of the numbers that share a common factor with 15. In other words, we exclude the multiples of 3 and multiples of 5. The remaining numbers are \(\mathbb{Z}_{15}^{*}=\{1,2,4,7,8,11,13,14\}\).

    Since 11 is a prime, 0 is the only number in \(\mathbb{Z}_{11}\) that shares a common factor with 11. All the rest satisfy \(\operatorname{gcd}(x, 11)=1\). Hence, \(\mathbb{Z}_{11}^{*}=\{1,2, \cdots, 10\}\).

    Example

    We can use Sage \({ }^{3}\) to play around with these concepts. Sage supports the % operator for modulus:

     

    It also supports a convenient way to generate " \(\mathbb{Z}_{n}\)-objects," or Mod-objects as they are called. An object like \(\operatorname{Mod}(2,15)\) represents the value \(2 \in \mathbb{Z}_{15}\), and all of its operations are overloaded to be the \(\bmod -15\) operations:

     

    In Sage, you can compute multiplicative inverses in a few different ways:

     

    Sage is smart enough to know when a multiplicative inverse doesn’t exist:

     

    Sage supports huge integers, with no problem:

     

    The relationship between multiplicative inverses and GCD goes even farther than Theorem 13.3. Recall that we can compute gcd \((x, n)\) efficiently using Euclid’s algorithm. There is a relatively simple modification to Euclid’s algorithm that also computes the corresopnding Bezout coefficients with little extra work. In other words, given \(x\) and \(n\), it is possible to efficiently compute integers \(a, b\), and \(d\) such that

    \[a x+b n=d=\operatorname{gcd}(x, n)\]

    In the case where \(\operatorname{gcd}(x, n)=d=1\), the integer \(a\) is a multiplicative inverse of \(x\) mod \(n\). The "extended Euclidean algorithm" for GCD is given below:

    fig-ch01_patchfile_01.jpg
    Figure \(\PageIndex{1}\): Copy and Paste Caption here. (Copyright; author via source)
    Example

    Sage implements the extended Euclidean algorithm as " \(x g c d^{\prime \prime:}\)

     

    You can then see that 223 and 427 are multiplicative inverses mod 529:

     

    The Totient Function

    Euler’s totient function is defined as \(\phi(n) \stackrel{\text { def }}{=}\left|\mathbb{Z}_{n}^{*}\right| ;\) that is, the number of elements of \(Z_{n}\) that have multiplicative inverses.

    As an example, if \(n\) is a prime, then \(\mathbb{Z}_{n}^{*}=\mathbb{Z}_{n} \backslash\{0\}\) because every integer in \(\mathbb{Z}_{n}\) apart from zero is relatively prime to \(n\). Therefore, \(\phi(n)=n-1\) in this case.

    RSA involves a modulus \(n\) that is the product of two distinct primes \(n=p q\). In that case, \(\phi(n)=(p-1)(q-1)\). To see why, let’s count how many elements in \(\mathbb{Z}_{p q}\) share a common divisor with \(p q\) (i.e., are not in \(\left.\mathbb{Z}_{p q}^{*}\right)\).

    • The multiples of \(p\) share a common divisor with \(p q\). These include \(0, p, 2 p, 3 p, \ldots,(q-1) p\). There are \(q\) elements in this list.
    • The multiples of \(q\) share a common divisor with \(p q\). These include \(0, q, 2 q, 3 q, \ldots,(p-1) q\). There are \(p\) elements in this list.

    We have clearly double-counted element 0 in these lists. But no other element is double counted. Any item that occurs in both lists would be a common multiple of both \(p\) and \(q\), but since \(p\) and \(q\) are relatively prime, their least common multiple is \(p q\), which is larger than any item in these lists.

    We count \(p+q-1\) elements of \(\mathbb{Z}_{p q}\) which share a common divisor with \(p q\). The rest belong to \(\mathbb{Z}_{p q}^{*}\), and there are \(p q-(p+q-1)=(p-1)(q-1)\) of them. Hence \(\phi(p q)=\) \((p-1)(q-1)\)

    General formulas for \(\phi(n)\) exist, but they typically rely on knowing the prime factorization of \(n\). We will see more connections between the difficulty of computing \(\phi(n)\) and the difficulty of factoring \(n\) later in this part of the course.

    The reason we consider \(\phi(n)\) at all is this fundamental theorem from abstract algebra:

    Theorem \(13.5\) (Euler’s Theorem)

    If \(x \in \mathbb{Z}_{n}^{*}\) then \(x^{\phi(n)} \equiv_{n} 1\).

    Example \(\PageIndex{1}\)

    Using the formula for \(\phi(n)\), we can see that \(\phi(15)=\phi(3 \cdot 5)=(3-1)(5-1)=8\). Euler’s theorem says that raising any element of \(\mathbb{Z}_{15}^{*}\) to the 8 power results in \(1:\) We can use Sage to verify this:

     


    \({ }^{2}\) "Group" is a technical term from abstract algebra.

    \({ }^{3}\) https://www.sagemath.org


    This page titled 13.1: “Dividing” Mod n 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?