 mersenneforum.org > Math Basic Number Theory 5: rationals & intro to modular arithmetic
 Register FAQ Search Today's Posts Mark Forums Read 2016-10-21, 20:48 #1 Nick   Dec 2012 The Netherlands 3×587 Posts Basic Number Theory 5: rationals & intro to modular arithmetic Let $$R$$ be a set of numbers, including 1, which is closed under subtraction and multiplication. We call an element $$x\in R$$ a unit of $$R$$ if there exists $$y\in R$$ such that $$xy=1$$. The set of all units of $$R$$ is called the unit group of $$R$$, written $$R^*$$. If $$xy=1$$, we call $$y$$ the multiplicative inverse (or simply inverse) of $$x$$, written $$x^{-1}$$. In the same way, $$x$$ is also the inverse of $$y$$. Thus the units of $$R$$ are the numbers in $$R$$ with a multiplicative inverse that is also present in $$R$$. Proposition 18 $$R^*$$ is closed under multiplication. proof Take any $$a,b\in R^*$$. Then there exist $$c,d\in R$$ such that $$ac=1$$ and $$bd=1$$. So $$(ab)(dc)=a(bd)c=ac=1$$, and $$dc\in R$$ (since $$R$$ is closed under multiplication) hence $$ab\in R^*$$. ∎ Example $$\mathbb{Z}^*=\{1,-1\}$$. The units of $$\mathbb{Z}$$ are the integers which divide 1 (exercise 7) and hence divide every integer (exercise 5). But it is something special when one integer divides another - all the work we have done so far stems from that. So it should not surprise us that the units of $$\mathbb{Z}$$ are only the trivial cases of 1 and -1. There are two standard ways of deriving new number systems from the integers with more interesting unit groups. We consider each of them in turn. A rational number is a number which can be expressed as a fraction $$\frac{a}{b}$$ where $$a$$ and $$b$$ are integers with $$b\neq 0$$. We write $$\mathbb{Q}$$ for the set of all rational numbers (this comes from the word "quotient"). For all $$n\in\mathbb{Z}$$, we have $$n=\frac{n}{1}\in\mathbb{Q}$$ so $$\mathbb{Z}\subset\mathbb{Q}$$. Any rational number can be written in infinitely many ways, of course, e.g. $$\frac{1}{2}=\frac{2}{4}=\frac{3}{6}=\ldots$$. If we take any rational number $$\frac{a}{b}$$ and let $$a'=\frac{a}{\gcd(a,b)}$$ and $$b'=\frac{b}{\gcd(a,b)}$$ then $$\frac{a'}{b'}=\frac{a}{b}$$ with $$\gcd(a',b')=1$$ (exercise 12), so we may choose the numerator and denominator in such a way that they are coprime. And $$\frac{-a'}{-b'}=\frac{a'}{b'}$$ so we may choose numerator and denominator so that the denominator is postive as well. Under these 2 conditions, the numerator and denominator of a fraction are uniquely determined (proving this is exercise 22 below). However, for calculating with rational numbers, it does not matter which representation as a fraction we use. For any sets $$A$$ and $$B$$, we write $$A\setminus B$$ for the set of all elements of $$A$$ which are not elements of $$B$$. Examples $$\{1,2,3\}\setminus\{3,4,5\}=\{1,2\}$$. $$\mathbb{Z}\setminus 2\mathbb{Z}$$ is the set of all odd numbers. Proposition 19 $$\mathbb{Q}^*=\mathbb{Q}\setminus\{0\}$$. proof $$\mathbb{Q}^*$$ is a subset of $$\mathbb{Q}$$ (by definition) and, for all $$y\in\mathbb{Q}$$, $$0y=0\neq 1$$ so $$0\notin\mathbb{Q}^*$$. Thus $$\mathbb{Q}^*\subset\mathbb{Q}\setminus\{0\}$$. Conversely, any element of $$\mathbb{Q}\setminus\{0\}$$ can be written in the form $$\frac{a}{b}$$ for some integers $$a$$ and $$b$$ both non-zero, so $$\frac{b}{a}$$ is also an element of $$\mathbb{Q}$$ and $$\frac{a}{b}\cdot\frac{b}{a}=\frac{ab}{ba}=1$$ hence $$\frac{a}{b}\in\mathbb{Q}^*$$. Thus $$\mathbb{Q}\setminus\{0\}\subset\mathbb{Q}^*$$ too, hence $$\mathbb{Q}^*=\mathbb{Q}\setminus\{0\}$$. ∎ We can visualize the rational numbers by associating them with points on a line, in the usual way: There is a point on the line for each rational number. But is there a rational number for each point on the line? Equivalently, can every possible length be given as the ratio between two integers? Proposition 20 $$\sqrt{2}\notin\mathbb{Q}$$. proof Suppose not. Then $$\sqrt{2}=\frac{r}{s}$$ for some integers $$r,s$$ which we may choose to be positive (since $$\sqrt{2}>0$$) and coprime. By theorem 15, we can write them each as a product of prime numbers: $$r=p_1p_2p_3\ldots p_n$$ and $$s=q_1q_2q_3\ldots q_m$$ where $$m,n$$ are non-negative integers and $$p_1,p_2,\ldots,p_n,q_1,q_2,\ldots,q_m$$ prime numbers with $$p_1\leq p_2\leq\ldots\leq p_n$$ and $$q_1\leq q_2\leq\ldots\leq q_m$$. So the prime factorization of $$r^2$$ is $$p_1p_1p_2p_2\ldots p_np_n$$, in which each prime number occurs an even number of times, while the prime factorization of $$2s^2$$ is $$2q_1q_1q_2q_2\ldots q_mq_m$$, in which the prime number 2 occurs an odd number of times. As prime factorizations are unique, it follows that $$r^2\neq 2s^2$$ hence $$\frac{r}{s}\neq\sqrt{2}$$, a CONTRADICTION. ∎ Thus the point on our line at a distance of $$\sqrt{2}$$ to the right of 0 has no rational number associated with it (and there are many more such points). If we enlarge the set $$\mathbb{Q}$$ to a set with a number corresponding to each point on the line, we get the set of all real numbers, which we write as $$\mathbb{R}$$. These are just the ordinary numbers that we all know from school. Elements of $$\mathbb{R}\setminus\mathbb{Q}$$ (i.e. real numbers that are not rational, such as $$\sqrt{2}$$) are called irrational numbers. We can prove something far more general than the previous proposition: Proposition 21 Let $$n$$ be a positive integer and $$a_0,a_1,a_2,\ldots,a_n$$ integers. For each rational number $$x$$, let $$f(x)$$ be the rational number given by $f(x)=a_0+a_1x+a_2x^2+a_3x^3+\ldots +a_nx^n.$ Suppose that $$a_n=1$$. Then, for all rational numbers $$x$$, if $$f(x)=0$$ then $$x$$ is an integer. proof Take any rational number $$x$$ with $$f(x)=0$$. Then $$x=\frac{r}{s}$$ for some integers $$r,s$$, and we may choose them so that $$r$$ and $$s$$ are coprime and $$s>0$$. We have $$a_0+a_1\frac{r}{s}+a_2\left(\frac{r}{s}\right)^2+\ldots +a_{n-1}\left(\frac{r}{s}\right)^{n-1}+\left(\frac{r}{s}\right)^n=0$$ so, working in the integers, $$a_0s^n+a_1rs^{n-1}+a_2r^2s^{n-2}+\ldots+a_{n-1}r^{n-1}s+r^n=0$$, and therefore $$s(-a_0s^{n-1}-a_1rs^{n-2}-a_2r^2s^{n-3}-\ldots-a_{n-1}r^{n-1})=r^n$$. Thus $$s|r^n$$. Take any prime number $$p$$. If $$p|s$$ then, since $$s|r^n$$, we also have $$p|r^n$$ (exercise 5), and $$p$$ is prime so $$p|r$$ (by lemma 14). But then $$p$$ is a common divisor of $$r$$ and $$s$$ so $$\gcd(r,s)\geq p$$, which is a CONTRADICTION (we chose $$r$$ and $$s$$ to be coprime). Hence no prime number divides $$s$$, so the prime factorization of $$s$$ is the product of no prime numbers, and therefore $$s=1$$, and $$x=\frac{r} {s}=r$$ which is an integer. ∎ Example Take any positive integer $$n$$. Then $$\sqrt{n}$$ is either an integer or it is irrational. This is the particular case $$f(x)=x^2-n$$ in proposition 21. For the second way of deriving a new number system from $$\mathbb{Z}$$, imagine taking the number line and rolling it up just tightly enough for 5 to appear directly over 0 (one layer higher in the roll), 6 above 1, etc. We shall regard two integers as equivalent if one appears directly over the other in this roll, i.e. if their difference is divisible by 5. For example, 14 appears above -1 so we say 14 is congruent to -1 (modulo 5) and write $$14\equiv -1\pmod{5}$$. We can also collect together integers that are equivalent with each other, and in this way we obtain the following 5 sets of integers: $\begin{array}{c} \{\ldots,-5,0,5,10,15,\ldots\} \\ \{\ldots,-4,1,6,11,16,\ldots\} \\ \{\ldots,-3,2,7,12,17,\ldots\} \\ \{\ldots,-2,3,8,13,18,\ldots\} \\ \{\ldots,-1,4,9,14,19,\ldots\} \end{array}$ Each integer occurs in precisely one of the above sets, is equivalent to all other integers in the same set and not equivalent to any integers in the other sets. We call these sets the equivalence classes of integers modulo 5. (Some people call them residue classes or congruence classes instead, but the meaning is the same.) For each integer $$n$$, let us write $$\bar{n}$$ for the equivalence class of $$n$$, i.e. the set in the above list of which $$n$$ is an element. Then, for example, $$\bar{7}=\bar{2}$$ since 7 and 2 occur in the same set, and this is another way of stating that $$7\equiv 2\pmod{5}$$. Proposition 22 For all integers $$a,b,c,d$$, if $$\bar{a}=\bar{c}$$ and $$\bar{b}=\bar{d}$$ then $$\overline{a+b}=\overline{c+d}$$, $$\overline{-a}=\overline{-c}$$ and $$\overline{ab}=\overline{cd}$$. proof Take any integers $$a,b,c,d$$ with $$\bar{a}=\bar{c}$$ and $$\bar{b}=\bar{d}$$. Then $$5|c-a$$ and $$5|d-b$$ so $$c-a=5m$$ and $$d-b=5n$$ for some integers $$m,n$$. Thus $$(c+d)-(a+b)=(c-a)+(d-b)=5(m+n)$$ so $$5|(c+d)-(a+b)$$ and therefore $$\overline{a+b}=\overline{c+d}$$. Also, $$(-c)-(-a)=a-c=5(-m)$$ so $$5|(-c)-(-a)$$ giving $$\overline{-a}=\overline{-c}$$. And $$cd-ab=c(d-b)+b(c-a)=5(cn+bm)$$ so $$5|cd-ab$$ hence $$\overline{ab}=\overline{cd}$$. ∎ It follows that we may define addition, subtraction and multiplication of equivalence classes, using any element from each class to represent it. To add two equivalence classes, for example, we simply choose an element from each, add the elements together, and then take the equivalence class in which their sum is found. Subtraction and multiplication work similarly, and the results do not depend on our choices (by proposition 22). To put this in formal language, for all integers $$a,b$$ we define $$\bar{a}+\bar{b}=\overline{a+b}$$, $$-\bar{a}=\overline{-a}$$ and $$\bar{a}\cdot\bar{b}=\overline{ab}$$. We write $$\mathbb{Z}/5\mathbb{Z}$$ for the set of all equivalence classes modulo 5 (this is the set whose elements are the 5 sets of integers listed above). Thus we have a new number system, in which each "number" is actually a set of integers, but can be represented by any one of them. Just as with fractions, we can write each "number" in this system in more than one way, but it does not matter which we choose when calculating. In a computer, the fixed representatives 0,1,2,3 & 4 are usually chosen but when calculating by hand it is often better to use -2,-1,0,1 & 2. The natural question which remains is: what are the units of $$\mathbb{Z}/5\mathbb{Z}$$? Proposition 23 Let $$R=\mathbb{Z}/5\mathbb{Z}$$. Then $$R^*=R\setminus\{\bar{0}\}$$. proof In the integers modulo 5: $\begin{eqnarray*} \bar{1}^2 & = & \bar{1} \\ \bar{2}\times\bar{3} & = & \bar{1} \\ \bar{4}^2 & = & \overline{-1}^2=\bar{1} \end{eqnarray*}$ so all elements of $$R$$ except $$\bar{0}$$ are units. For all integers $$n$$, $$\bar{n}\cdot\bar{0}=\bar{0}\neq\bar{1}$$ so $$\bar{0}$$ is not a unit. ∎ We could replace 5 with any other postive integer throughout this construction and get the same results, except in proposition 23. Exercises 22. Let $$a,b,c,d$$ be integers with $$b>0$$, $$d>0$$, $$\frac{a}{b}=\frac{c} {d}$$, $$\gcd(a,b)=1$$ and $$\gcd(c,d)=1$$. Show that $$a=c$$ and $$b=d$$. 23. The Archimedan property of the real numbers states that, for all $$x\in\mathbb{R}$$, there exists $$n\in\mathbb{Z}$$ such that $$n>x$$. Use this property to prove that, for all $$x,y\in\mathbb{R}$$ with \(x 2016-10-21, 22:21 #2 chalsall If I May   "Chris Halsall" Sep 2002 Barbados 2·7·727 Posts I understand and appreciate that. Tonight I came up to find that my cats had eaten my chickens. Many feathers; many wings. Many cats not desiring dinner.  Thread Tools Show Printable Version Email this Page Similar Threads Thread Thread Starter Forum Replies Last Post Nick Number Theory Discussion Group 17 2017-12-23 20:10 Nick Number Theory Discussion Group 5 2017-04-25 14:32 Nick Number Theory Discussion Group 0 2017-01-19 20:22 Nick Number Theory Discussion Group 0 2017-01-07 13:15 Nick Number Theory Discussion Group 0 2016-12-29 13:47

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

Sun Jan 16 10:34:50 UTC 2022 up 177 days, 5:03, 0 users, load averages: 0.89, 0.88, 0.93