Differences
This shows you the differences between two versions of the page.
— |
modular:residue_classes [2015/03/19 20:00] (current) aleksei imported from previous wiki |
||
---|---|---|---|
Line 1: | Line 1: | ||
+ | ===== Residue classes ===== | ||
+ | Modular arithmetics as a way of calculating modulo some number $n$ is a powerful tool. However, it can be made simpler, and thus even more effective. | ||
+ | |||
+ | First, recall that numbers having the same remainder when divided by $n$ behave in exactly the same way in such a calculation and yield exactly the same results. | ||
+ | |||
+ | A quick example: | ||
+ | $8 * 4 + 11 \equiv 3*(-1) + 6 \equiv 3 (\mod 5)$. | ||
+ | |||
+ | One might say that | ||
+ | there are only | ||
+ | $n$ //essentially different objects// for this calculation - the numbers that give distinct remainders modulo $n$. The numbers having the same remainder can be considered to be //essentially the same object//. | ||
+ | |||
+ | The next step would be to | ||
+ | //define// **addition** and **multiplication** between such objects in a suitable way compatible with the original addition and multiplication. | ||
+ | |||
+ | This approach leads us to the notion of **residue classes**. | ||
+ | |||
+ | A residue class modulo $n$ is a set of all integers that give the same remainder when divided by $n$. | ||
+ | <WRAP def> | ||
+ | Formally, the residue class of $a \in \mathbb Z$ modulo $n \in \mathbb N$ is | ||
+ | $\overline a = \{b \in \mathbb Z \mid a \equiv b \ (\mod n)\} = \{a + kn \mid k \in \mathbb Z\}$. | ||
+ | In this notation, the modulus $n$ is implicit. | ||
+ | </WRAP> | ||
+ | As the following exercises show, all residue | ||
+ | classes modulo $n$ partition the set $\mathbb Z$ into $n$ parts. | ||
+ | <WRAP task> | ||
+ | Show that for all $a, b \in \mathbb Z$, the following three claims are equivalent: | ||
+ | * $\overline a = \overline b$, | ||
+ | * $\overline a \cap \overline b = \emptyset$, | ||
+ | * $a \equiv b \ (\mod n)$, | ||
+ | * exists $k \in \mathbb Z$, such that $a = b + kn$. | ||
+ | </WRAP> | ||
+ | <WRAP task> | ||
+ | Show that $\overline 0, \overline 1, \dots , \overline{n − 1}$ are different residue classes. | ||
+ | </WRAP> | ||
+ | The first of those two exercises shows that there are at most $n$ different residue | ||
+ | classes modulo $n$, because there are $n$ different remainders when dividing by $n$. The | ||
+ | second exercise shows that the number of residue classes is at least $n$. | ||
+ | |||
+ | <WRAP def> | ||
+ | Denote $\mathbb Z_n = \{\overline 0, \overline 1, \dots , \overline{n − 1}\}$. | ||
+ | </WRAP> | ||
+ | |||
+ | We can define addition and multiplication on $\mathbb Z_n$ as | ||
+ | follows: | ||
+ | *$\overline a+\overline b=\overline{a+b}$, | ||
+ | *$\overline a \cdot \overline b=\overline{a\cdot b}$. | ||
+ | Thanks to the properties of $\equiv$, shown in the previous section, these operations are well-defined. | ||
+ | Namely, when we write $\overline{a + b}$, the integer $a$ is only defined as an arbitrary element of the | ||
+ | residue class $\overline a$. When we take an arbitrary element $a$ of $\overline a$, and an arbitrary element $b$ of | ||
+ | $\overline b$, is it the case that the residue class $\overline{a + b}$ is always the same? | ||
+ | Yes, because $a_1 + b_1 \equiv a_2 + b_2 \ (\mod n)$ whenever | ||
+ | $a_1 \equiv a_2 \ (\mod n)$ and $b_1 \equiv b_2 \ (\mod n)$. Similarly, the multiplication of residue classes is well-defined. | ||
+ | |||
+ | Having defined $\mathbb Z_n$, we can rewrite our quick example from the beginning of the lesson as | ||
+ | $\overline{8} \cdot \overline 4 + \overline{11}= \overline 3 \cdot \overline{-1} +\overline 6 = \overline{3}$ in $\mathbb Z_5$, where the first equality holds trivially simply because the corresponding objects are equal. | ||
+ | |||
+ | <WRAP task> | ||
+ | Write down the addition and multiplication tables for $\mathbb Z_7$ and $\mathbb Z_8$. | ||
+ | </WRAP> | ||
+ | |||
+ | ==Similarities to integers== | ||
+ | |||
+ | It turns out that | ||
+ | both operations of addition and multiplication on $\mathbb Z_n$ have similar properties | ||
+ | as the same operations on integers: | ||
+ | |||
+ | *They are both **associative**, meaning $(\overline a + \overline b) + \overline c = \overline a + (\overline b + \overline c)$ and $(\overline a \cdot \overline b) \cdot \overline c = \overline a \cdot (\overline b \cdot \overline c)$.\\ This property allows the formula $\overline a + \overline b + \overline c$ to be correctly understood in a single way. The same is true for $a \cdot b \cdot c$. | ||
+ | | ||
+ | *They are both **commutative**, meaning $\overline a + \overline b = \overline b + \overline a$ and $\overline a \cdot \overline b = \overline b \cdot \overline a$. | ||
+ | | ||
+ | *They both have **units**. For addition, $\overline a + \overline 0 = \overline 0 + \overline a = \overline a$. For multiplication, $\overline a \cdot \overline 1 = \overline 1 \cdot \overline a = \overline a$. | ||
+ | |||
+ | *There is always an **opposite element** for addition, meaning that for any $\overline a$ there exists $-\overline a = \overline{-a}$ such that $\overline a + -\overline{a} = \overline{0}$. | ||
+ | |||
+ | *Multiplication is **distributive** over addition:\\ \begin{align*} | ||
+ | (\overline a+\overline b)\cdot \overline c &= \overline a\cdot \overline c + \overline b\cdot \overline c\enspace,\\ | ||
+ | \overline a\cdot (\overline b + \overline c) &= \overline a\cdot \overline c + \overline a\cdot \overline c\enspace. | ||
+ | \end{align*} | ||
+ | |||
+ | These properties actually mean that both $\mathbb Z$ | ||
+ | and $\mathbb Z_n$ | ||
+ | are **commutative rings** with respect to addition and multiplication. For an introduction to rings, see ?. | ||
+ | |||
+ | Because of the latter fact $\mathbb Z_n$ | ||
+ | is also called the **residue class ring modulo $n$**. | ||
+ | |||
+ | |||
+ | <WRAP thtask> | ||
+ | Show that $\mathbb Z_n$, together with the addition and multiplication operations, is a commutative ring. | ||
+ | </WRAP> | ||
+ | ==Differences== | ||
+ | |||
+ | Not everything in $\mathbb Z_n$ is the same way as in $\mathbb Z$. | ||
+ | |||
+ | Take the equation $4a = 4b$ with integers $a$ and $b$. We know that it yields $a = b$. | ||
+ | More generally, for any integer $c \neq 0$ | ||
+ | the equality $ca = c b$ | ||
+ | implies $a = b$ because we can divide both sides by $c$. | ||
+ | On the other hand, for example, in $\mathbb Z_{12}$ | ||
+ | the equality | ||
+ | $\overline{4}\cdot \overline{a} = \overline{4}\cdot \overline{b}$ does not necessarily mean that | ||
+ | $\overline{a} = \overline{b}$, simply because | ||
+ | $\overline{4}\cdot \overline{1} = \overline{4}\cdot \overline{4}$. | ||
+ | |||
+ | The numbers as the number $c$ above are called **cancellative**. | ||
+ | |||
+ | Thus we made an important observation that | ||
+ | every nonzero integer is cancellative while for some numbers $n$ there are nonzero nonconcellative elements of $\mathbb Z_n$. | ||
+ | |||
+ | <WRAP task> | ||
+ | Find noncancellative elements of $\mathbb Z_{12}$, | ||
+ | $\mathbb Z_7$, and $\mathbb Z_4$. | ||
+ | |||
+ | ++Answer|For $\mathbb Z_{12}: \overline 0, \overline 2, \overline 3, \overline 4, \overline 6, \overline 8, \overline 9, \overline{10}$, | ||
+ | ++ | ||
+ | </WRAP> | ||
+ | |||
+ | Similarly, consider the equation $ab = 0$ with integers $a$ and $b$. It means that at least one of the numbers $a$ and $b$ is equal to $0$. Again, | ||
+ | this is not the case in $\mathbb Z_{12}$ because we can find nonzero $\overline{a}$ and $\overline b$ | ||
+ | such that $\overline{a} \cdot \overline{b} = \overline{0}$, e.g., $\overline{4} \cdot \overline{3} = \overline{0}$. | ||
+ | |||
+ | Nonzero $a$ such that $ab = 0$ for some nonzero $b$ is called a **zero divisor**. | ||
+ | |||
+ | Thus we observed that there are no zero divisors in $\mathbb Z$ but for some numbers $n$ there are zero divisors in $\mathbb Z_n$. | ||
+ | |||
+ | It is relatively easy to see that a zero divisor is always noncancellative. | ||
+ | |||
+ | <WRAP thtask> | ||
+ | Show that a zero divisor is never cancellative. | ||
+ | ++Solution|Assume that a zero divisor $a$ is cancellative. Then for some $b \neq 0$, we know that $ab = 0$. On the other hand, $a0 = 0$. Then $ab = a0$ but $b \neq 0$. So our assumption was wrong and $a$ is not cancellative.++ | ||
+ | </WRAP> | ||
+ | It turns out that in $\mathbb Z_n$ the notions of zero divisors and noncancellative nonzero elements actually coincide. In fact, a nonzero element $\overline a$ in $\mathbb Z_n$ is a zero divisor and noncancellative if and only if | ||
+ | $\gcd(a,n) > 1$. | ||
+ | ++++Proof| | ||
+ | Let us check this fact. To see that $\gcd(a,n) > 1$ implies that $\overline a$ is a zero divisor, let us recall the equality $\gcd(a,n) \cdot \operatorname{lcm}(a,n) = an$. From this we have | ||
+ | $a \cdot \frac{n}{\gcd(a,n)} = \operatorname{lcm}(a,n)$. Let us denote $c :=\frac{n}{\gcd(a,n)}$ and notice that $c$ is an integer greater than $1$ but less than $n$, so that $c \not \equiv 0 (\mod n)$. In other words, | ||
+ | $\overline c \neq 0$. But $\overline a \cdot \overline c = \overline{\operatorname{lcm}(a,n)} = \overline 0$. So $\overline a$ is a zero divisor. | ||
+ | |||
+ | On the other hand, if $\gcd(a,n) = 1$, then Bezout's identity says that | ||
+ | there are integers $x$ and $y$ such that $ax + ny = 1$. | ||
+ | Then $ax \equiv 1 (\mod n)$ and therefore $\overline a \cdot \overline x = \overline 1$. It means that $\overline x$ is the **multiplicative inverse** of $\overline a$ in $\mathbb Z_n$. | ||
+ | It follows easily that $\overline a$ is cancellative because | ||
+ | $\overline a \cdot \overline b = \overline a \cdot \overline c$ | ||
+ | would imply $\overline x \cdot \overline a \cdot \overline b = \overline x \cdot \overline a \cdot \overline c$, then | ||
+ | $\overline 1 \cdot \overline b = \overline 1 \cdot \overline c$, | ||
+ | and $\overline b = \overline c$ | ||
+ | ++++ | ||
+ | |||
+ | As we already observed in the proof, the condition $\gcd(a,n) = 1$ | ||
+ | actually describes those elements in $\mathbb Z_n$, which have **multiplicative inverse**. That is, those elements $\overline a$ for which there is $x \in \mathbb Z_n$ such that $\overline a \cdot \overline x = \overline x \cdot \overline a = \overline 1$. For example, in $\mathbb Z_7$ | ||
+ | the multiplicative inverse of $\overline 3$ is $\overline 5$, because | ||
+ | $\overline 3 \cdot \overline 5 = \overline 1$ in $\mathbb Z_7$. | ||
+ | Then $\overline x$ is denoted by $\overline a^{-1}$. If $\overline a$ | ||
+ | has a multiplicative inverse, then $\overline a$ is called a **unit** in $\mathbb Z_n$. | ||
+ | In our example, $\overline 3$ is a unit and $\overline 3^{-1} = \overline 5$ in $\mathbb Z_7$. | ||
+ | |||
+ | <WRAP task> | ||
+ | Find multiplicative inverses of units in $\mathbb Z_{12}$, $\mathbb Z_7$, $\mathbb Z_{20}$. Remember that units in $\mathbb Z_n$ are exactly those elements $a$ for which $\gcd(a,n) = 1$. | ||
+ | </WRAP> | ||
+ | |||
+ | As you may have noticed... | ||