20161028, 23:06  #1 
Dec 2012
The Netherlands
711_{16} Posts 
Basic Number Theory 6: functions and the Chinese Remainder Theorem
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: Code:
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 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 11 = 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 \(m1\) inclusive and \(b\) an integer from 0 to \(n1\) 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,mn1\}\)). 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,mn1\}\), if \(f(a)=f(b)\) then \(a\equiv b\pmod{m}\) and \(a\equiv b\pmod{n}\), so \(mab\) and \(nab\). As \(\gcd(m,n)=1\), it follows by proposition 28 that \(mnab\). But \(mn<ab<mn\) so \(ab=0\) and therefore \(a=b\). Thus \(f\) is injective. Now take any \(b\in\{0,1,\ldots,m1\}\) and any \(c\in\{0,1,\ldots,n1\}\). 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=1rm\), we have \(a=m(crbr)+b\) so \(a\bmod{m}=b\). Similarly, \(rm=1sn\) so \(a=n(bscs)+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,mn1\}\), and put \(a'=a\bmod{m}\) and \(b'=b\bmod{m}\). Suppose first that \(a+b\bmod{mn}=c\). Then \(mna+bc\) so \(ma+bc\) (by proposition 28) and therefore \(ma'+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 \(mnabc\) so \(mabc\) and therefore \(ma'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}\). 
20161031, 15:41  #2 
Romulan Interpreter
"name field"
Jun 2011
Thailand
3×23×149 Posts 
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). Code:
\ 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 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. Last fiddled with by LaurV on 20161031 at 15:59 Reason: table format 
20161031, 19:38  #3  
Dec 2012
The Netherlands
3^{3}×67 Posts 
Quote:
(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.) 

20161031, 20:52  #4  
"Forget I exist"
Jul 2009
Dartmouth NS
20342_{8} Posts 
Quote:
Last fiddled with by science_man_88 on 20161031 at 20:52 

20161031, 22:26  #5  
Dec 2012
The Netherlands
3^{3}·67 Posts 
Quote:
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 crosssection circle. 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Sorting on chinese remainder theorem  alpertron  Math  23  20171215 16:46 
Complexity of Chinese Remainder Theorem  carpetpool  Miscellaneous Math  4  20170209 19:26 
Basic Number Theory 15: Lagrange's theorem, cyclic groups and modular arithmetic  Nick  Number Theory Discussion Group  0  20170107 13:15 
Basic Number Theory 8: equiv. relations and Fermat's little theorem  Nick  Number Theory Discussion Group  0  20161110 23:10 
Implementing Chinese Remainder Theorem in C  ShiningArcanine  Software  3  20071117 05:55 