 mersenneforum.org > Math Basic Number Theory 6: functions and the Chinese Remainder Theorem
 Register FAQ Search Today's Posts Mark Forums Read 2016-10-28, 23:06 #1 Nick   Dec 2012 The Netherlands 110111000012 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 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 2016-10-31, 15:41 #2 LaurV Romulan Interpreter   "name field" Jun 2011 Thailand 268316 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 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. Last fiddled with by LaurV on 2016-10-31 at 15:59 Reason: table format   2016-10-31, 19:38   #3
Nick

Dec 2012
The Netherlands

3×587 Posts Quote:
 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.)   2016-10-31, 20:52   #4
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

26·131 Posts Quote:
 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.

Last fiddled with by science_man_88 on 2016-10-31 at 20:52   2016-10-31, 22:26   #5
Nick

Dec 2012
The Netherlands

3×587 Posts Quote:
 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.  Thread Tools Show Printable Version Email this Page Similar Threads Thread Thread Starter Forum Replies Last Post alpertron Math 23 2017-12-15 16:46 carpetpool Miscellaneous Math 4 2017-02-09 19:26 Nick Number Theory Discussion Group 0 2017-01-07 13:15 Nick Number Theory Discussion Group 0 2016-11-10 23:10 ShiningArcanine Software 3 2007-11-17 05:55

All times are UTC. The time now is 10:47.

Sun Jan 16 10:47:00 UTC 2022 up 177 days, 5:15, 0 users, load averages: 0.95, 0.87, 0.87