Basic Number Theory 6: functions and the Chinese Remainder Theorem

[Nick]

Suppose someone thinks of a positive integer \(n\) and tells you the last digit (in decimal). You could then easily give the remainders on dividing \(n\) by 5 and by 2.
What is remarkable is that this works the other way around as well: if you are told the remainders on dividing \(n\) by 5 and by 2, then you can work out what the last digit of \(n\) is.
Writing \(n\) mod 10 for the remainder on dividing \(n\) by 10, and similarly for 5 and 2, we get the following table:

n mod 10  n mod 5  n mod 2
   0         0        0
   1         1        1
   2         2        0
   3         3        1
   4         4        0
   5         0        1
   6         1        0
   7         2        1
   8         3        0
   9         4        1

There are 5 possible remainders on division by 5 and 2 possible remainders on division by 2, so there are 10 possible pairs of remainders, and each of these pairs appears exactly once in the above table.
This is a simple case of a famous result which we call the Chinese Remainder Theorem (since it was known to Chinese mathematicians already in the 13th century).
Before looking at that theorem in detail, we need to recall (or learn!) some general mathematical definitions and notation for functions.

Let \(A\) and \(B\) be sets.
A function from \(A\) to \(B\) is a rule or method associating each element of \(A\) with a unique element of \(B\).
Conceptually, we may think of it as something you do to an element of \(A\) that results in an element of \(B\).
If \(f\) is such a function and \(a\) an element of \(A\), then we write \(f(a)\) for the associated element of \(B\) and call it the image of \(a\) under \(f\).
The set \(A\) is called the domain of the function, and \(B\) the codomain.
The set \(\{f(a):a\in A\}\) of all images of elements of \(A\) under \(f\) is called the image of the function \(f\), denoted im(\(f\)) or \(f(A)\). It is a subset of \(B\).
The notation \(f:A\rightarrow B\) means that \(f\) is a function from \(A\) to \(B\).
A barred arrow may be used to specify the effect of \(f\) on elements of \(A\).
For example, \(f:\mathbb{R}\rightarrow\mathbb{R},x\mapsto x^2\) means \(f\) is the function such that, for each real number \(x\), \(f(x)\) is the real number \(x^2\).
This notation gives the domain, codomain and the rule for the function \(f\), and it is important to give all three when specifying a function.
Functions \(f:A\rightarrow B\) and \(g:C\rightarrow D\) are equal if (and only if) \(A=C\), \(B=D\) and, for all \(x\in A\), \(f(x)=g(x)\).

Let \(f\) be a function from \(A\) to \(B\).
We say \(f\) is injective or call it an injection if, for all \(x,y\in A\), \(f(x)=f(y)\Rightarrow x=y\) (or, equivalently, \(x\neq y\Rightarrow f(x)\neq f(y)\)).
We say \(f\) is surjective or call it a surjection if, for all \(b\in B\) there exists \(a\in A\) such that \(f(a)=b\).
We say \(f\) is bijective or call it a bijection if \(f\) is both injective and surjective.

Example
Let \(\mathbb{R}_{\geq 0}=\{x\in\mathbb{R}:x\geq 0\}\), and define
\(f:\mathbb{R}\rightarrow\mathbb{R},x\mapsto x^2\),
\(g:\mathbb{R}_{\geq 0}\rightarrow\mathbb{R},x\mapsto x^2\) and
\(h:\mathbb{R}_{\geq 0}\rightarrow\mathbb{R}_{\geq 0},x\mapsto x^2\).
Then \(f\) is not injective (e.g. f(-2)=f(2)) and \(f\) is not surjective either (e.g. -1 is an element of its codomain but, for all \(x\in\mathbb{R}\), \(f(x)\neq -1\)).
The function \(g\) is injective but not surjective, and the function \(h\) is both injective and surjective (hence bijective).

For any set \(A\), the identity function on \(A\) is the function \(i_A:A\rightarrow A,x\mapsto x\), which is bijective.

Some books use other words for the concepts we have defined so far.
Here is a translation table:
map or mapping means function (possibly with extra conditions attached)
source = domain
target = codomain
range = image of the function
1-1 = injective
onto = surjective

Let \(A\), \(B\) and \(C\) be sets, \(f\) a function from \(A\) to \(B\) and \(g\) a function from \(B\) to \(C\). The composition of \(g\) with \(f\), denoted \(g\circ f\) (say "\(g\) after \(f\)"), is the function from \(A\) to \(C\) given by \(x\mapsto g(f(x))\).

We show that composition of functions is associative:

Proposition 24
Let \(A,B,C,D\) be sets and \(f:A\rightarrow B\), \(g:B\rightarrow C\) and \(h:C\rightarrow D\) functions.
Then \((h\circ g)\circ f=h\circ (g\circ f)\).

proof
For all \(x\in A\),
\[ ((h\circ g)\circ f)(x)=(h\circ g)(f(x))=h(g(f(x))) =h((g\circ f)(x))=(h\circ (g\circ f))(x). \]∎

Let \(f\) be a function from \(A\) to \(B\) and \(g\) a function from \(B\) to \(A\).
We say \(g\) is an inverse for \(f\) (and \(f\) an inverse for \(g\)) if \(g\circ f=i_A\) and \(f\circ g=i_B\).
Intuively, \(g\) is an inverse for \(f\) if \(g\) undoes the effect of \(f\) and vice versa.

Proposition 25
A function \(f:A\rightarrow B\) has an inverse if and only if \(f\) is bijective.

proof
Suppose \(f\) has an inverse \(g:B\rightarrow A\).
Take any \(x,y\in A\) and suppose \(f(x)=f(y)\).
Then \(g(f(x))=g(f(y))\) but \(g(f(x))=i_A(x)=x\) and similarly \(g(f(y))=y\) so \(x=y\). Thus \(f\) is injective.
Take any \(b\in B\) and let \(a=g(b)\in A\).
Then \(f(a)=f(g(b))=i_B(b)=b\). So \(f\) is also surjective, and hence bijective.

Conversely, suppose that \(f\) is bijective.
Take any \(b\in B\).
As \(f\) is surjective, there exists an element \(a\in A\) such that \(f(a)=b\).
Moreover, this element \(a\in A\) is unique: for any \(x\in A\), if \(f(x)=b\) too then \(f(x)=f(a)\) so \(x=a\) since \(f\) is injective.
We define \(g(b)=a\) and do this in the same way for each \(b\in B\), giving a function \(g:B\rightarrow A\).
Then, for all \(b\in B\), \(f(g(b))=b\) so \(f\circ g=i_B\).
Now take any \(a\in A\), and let \(b=f(a)\).
By the above, we have \(f(g(b))=b\) so \(f(g(f(a)))=f(a)\) and \(f\) is injective so it follows that \(g(f(a))=a\).
This holds for all \(a\in A\), hence \(g\circ f=i_A\) as well, and therefore \(g\) is an inverse for \(f\). ∎

Proposition 26
Let \(f:A\rightarrow B\), \(g:B\rightarrow A\) and \(h:B\rightarrow A\) be functions.
If \(g\) and \(h\) are both inverses for \(f\) then \(g=h\).

proof
By proposition 24,
\[ g=g\circ id_B=g\circ (f\circ h)=(g\circ f)\circ h=id_A\circ h=h. \]∎

Thus if a function \(f\) is bijective then it has a unique inverse, which we denote by \(f^{-1}\).

Corollary 27
If \(f:A\rightarrow B\) is a bijection, then so is \(f^{-1}:B\rightarrow A\).

proof
We have \(f\circ f^{-1}=i_B\) and \(f^{-1}\circ f=i_A\) so \(f\) is the inverse of \(f^{-1}\) too, hence \(f^{-1}\) is bijective by proposition 25. ∎

For any finite set \(A\), we write \(\#A\) or \(|A|\) for the number of elements in \(A\).
The unique set with no elements is called the empty set. It has its own symbol: \(\emptyset\).
Thus \(\#A=0\Leftrightarrow A=\emptyset\).

For any sets \(A\) and \(B\), the Cartesian product of \(A\) with \(B\), written \(A\times B\), is the set of all ordered pairs \((a,b)\) with \(a\in A\) and \(b\in B\), where an ordered pair is defined so that \((a,b)=(c,d)\) if and only if \(a=c\) and \(b=d\).
We may write the Cartesian product of \(A\) with itself as \(A^2\).
For example, \(\mathbb{R}^2\) is the set of all ordered pairs of real numbers (corresponding with all points in a plane).

We have now established enough general mathematical language to be able to return to Number Theory.

Proposition 28
Let \(a,m,n\in\mathbb{Z}\) with \(\gcd(m,n)=1\).
Then \(mn\) divides \(a\) if and only if (\(m\) divides \(a\) and \(n\) divides \(a\)).

proof
If \(mn\) divides \(a\) then \(mnk=a\) for some integer \(k\), and so \(m\) divides \(a\) and \(n\) divides \(a\) too.
Conversely, suppose \(m\) and \(n\) each divide \(a\).
Then \(a=mr\) and \(a=ns\) for some integers \(r\) and \(s\).
As \(\gcd(m,n)=1\), there exist integers \(b\) and \(c\) such that \(bm+cn=1\) (by corollary 10), so \(bma+cna=a\) and therefore \(mn(bs+cr)=a\).
Hence \(mn\) divides \(a\). ∎

Take any positive integers \(m\) and \(n\) with \(\gcd(m,n)=1\).
The Cartesian product \(\mathbb{Z}/m\mathbb{Z}\times\mathbb{Z}/n\mathbb{Z}\) is the set of all ordered pairs \((a,b)\) where \(a\) is an integer from 0 to \(m-1\) inclusive and \(b\) an integer from 0 to \(n-1\) inclusive.
(Strictly speaking, they each represent an entire equivalence class of integers as described last time, but making this too complicated will obscure the idea of the theorem if you haven't seen it before.)
We can add, subtract and multiply such pairs by performing the operations on each coordinate individually, using modulo \(m\) arithmetic on the first coordinate and modulo \(n\) arithmetic on the second.
Formally, we define
\[\begin{eqnarray*}
(a,b)+(c,d) & = & (a+c\bmod{m},b+d\bmod{n}) \\
-(a,b) & = & (-a\bmod{m},-b\bmod{n}) \\
(a,b)(c,d) & = & (ac\bmod{m},bd\bmod{n})
\end{eqnarray*} \]
For example, in the case \(m=5\) and \(n=2\), we have \((4,1)+(1,1)=(0,0)\) since \(4+1\equiv 0\pmod{5}\) and \(1+1\equiv 0\pmod{2}\).

Theorem 29 The Chinese Remainder Theorem
Let \(m,n\) be integers with \(\gcd(m,n)=1\) and \(f\) the function from \(\mathbb{Z}/mn\mathbb{Z}\) to \(\mathbb{Z}/m\mathbb{Z}\times\mathbb{Z}/n\mathbb{Z}\) given by \(f(a)=(a\bmod{m},a\bmod{n})\) (where \(a\in\{0,1,2,\ldots,mn-1\}\)).
Then \(f\) is a bijection, and \(f\) preserves addition and multiplication:
if \(a+b=c\) in \(\mathbb{Z}/mn\mathbb{Z}\) then \(f(a)+f(b)=f(c)\) in \(\mathbb{Z}/m\mathbb{Z}\times\mathbb{Z}/n\mathbb{Z}\),
and if \(ab=c\) in \(\mathbb{Z}/mn\mathbb{Z}\) then \(f(a)f(b)=f(c)\) in \(\mathbb{Z}/m\mathbb{Z}\times\mathbb{Z}/n\mathbb{Z}\)

proof
For any \(a,b\in\{0,1,2,\ldots,mn-1\}\), if \(f(a)=f(b)\) then \(a\equiv b\pmod{m}\) and \(a\equiv b\pmod{n}\), so \(m|a-b\) and \(n|a-b\).
As \(\gcd(m,n)=1\), it follows by proposition 28 that \(mn|a-b\).
But \(-mn<a-b<mn\) so \(a-b=0\) and therefore \(a=b\).
Thus \(f\) is injective.
Now take any \(b\in\{0,1,\ldots,m-1\}\) and any \(c\in\{0,1,\ldots,n-1\}\).
As \(\gcd(m,n)=1\), there exist integers \(r,s\) such that \(rm+sn=1\) (by corollary 10).
Let \(a=crm+bsn\bmod{mn}\).
As \(sn=1-rm\), we have \(a=m(cr-br)+b\) so \(a\bmod{m}=b\).
Similarly, \(rm=1-sn\) so \(a=n(bs-cs)+c\) giving \(a\bmod{n}=c\).
Hence \(f(a)=(b,c)\). Thus \(f\) is also surjective, making \(f\) bijective.
Take any \(a,b,c\in\{0,1,\ldots,mn-1\}\), and put \(a'=a\bmod{m}\) and \(b'=b\bmod{m}\).
Suppose first that \(a+b\bmod{mn}=c\).
Then \(mn|a+b-c\) so \(m|a+b-c\) (by proposition 28) and therefore \(m|a'+b'-c\). So \(a'+b'\equiv c\pmod{m}\).
In the same way, \(a'+b'\equiv c\pmod{n}\) too, hence \(f(a)+f(b)=f(c)\).
Suppose instead that \(ab\bmod{mn}=c\)
Then \(mn|ab-c\) so \(m|ab-c\) and therefore \(m|a'b'-c\), giving \(a'b'\equiv c\pmod{m}\).
Similarly, \(a'b'\equiv c\pmod{n}\) too, hence \(f(a)f(b)=f(c)\). ∎

Exercises
27. Find examples of functions \(f\), \(g\) and \(h\) such that \(g\circ f=h\circ f\) but \(g\neq h\).
28. Let \(A\) and \(B\) be finite sets and suppose there exists an injection \(f\) from \(A\) to \(B\). Show by induction that \(\#A\leq\#B\). Conclude that if \(f\) is a bijection then \(\#A=\#B\).
29. Let \(f:A\rightarrow B\) and \(g:B\rightarrow C\) be functions.
Prove that if \(f\) and \(g\) are both injective, then so is \(g\circ f\).
Similarly, prove that if \(f\) and \(g\) are both surjective then so is \(g\circ f\).
30. Find all integers \(a\in\{0,1,2,\ldots,99\}\) such that \(a^2\equiv a\pmod{100}\).

[LaurV]

Beautiful.

When i give the example with the two modulus to someone, I like to make it in 2D, put one mod on the first row and the second mod on the first column, and start filling the table diagonally. Say you have (mod 5) and (mod 8).

      \   mod 5
mod 8  \   0  1  2  3  4
        \___________________
      0 |  0        8
      1 |     1        9
      2 | 10     2
      3 |    11     3
      4 |       etc    4
      5 |  5
      6 |     6
      7 |        7

Then continue to 39, all 5x8=40 numbers. For example 9, it is 1 (mod 8) and it is 4 (mod 5) so it stays in the row of 1 (second row), column of 4 (fifth column). It is very easy to see how they go diagonally and why the "gcd=1" condition is important, otherwise the diagonals will "overpose", step on each other tails. Try with other numbers... (with or without gcd=1). When you reach one end, wrap around from the first row or column, on the next column or row, respectively. See how the "mod" values go for both x and y, where to put them in the table.


Here, as gcd(5,8)=1, all the table can be filled going like that diagonally, and there is not conflict. All 40 numbers are used, and all 40 squares are taken. Try with (for example) 6 and 15. What is happening?

Also, they always start in (0,0), upper left corner, and always end in lower right corner (guess why, hehe), no matter if gcd=1 or not.

[Nick]

Originally Posted by LaurV

When i give the example with the two modulus to someone, I like to make it in 2D, put one mod on the first row and the second mod on the first column, and start filling the table diagonally...

That's a good way of visualizing what is going on!

(For anyone with good 3D intuition: imagine copying LaurV's table on to a piece of paper, then bending the top and bottom edges back until they meet each other and gluing them to make a cylinder (with the numbers on the outside). Now take the two cylinder ends and bend them around to meet each other and glue together. This gives a torus (doughnut) on which the sequence of numbers from 0 to 39 inclusive form a helix.)

[science_man_88]

Originally Posted by Nick

That's a good way of visualizing what is going on!

(For anyone with good 3D intuition: imagine copying LaurV's table on to a piece of paper, then bending the top and bottom edges back until they meet each other and gluing them to make a cylinder (with the numbers on the outside). Now take the two cylinder ends and bend them around to meet each other and glue together. This gives a torus (doughnut) on which the sequence of numbers from 0 to 39 inclusive form a helix.)

it's not called clock arithmetic for no reason in your donut example one clock is the donut shape in 2d and the other is the band that forms the structure of the donut itself.

[Nick]

Originally Posted by science_man_88

it's not called clock arithmetic for no reason in your donut example one clock is the donut shape in 2d and the other is the band that forms the structure of the donut itself.

Exactly!
In terms of the definitions we looked at above, a torus is a Cartesian product of 2 circles: each point on it is determined by 2 coordinates, the first giving how far round the big circle you are and the second giving the same for the cross-section circle.