mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math > Number Theory Discussion Group

Reply
 
Thread Tools
Old 2016-10-21, 20:48   #1
Nick
 
Nick's Avatar
 
Dec 2012
The Netherlands

2·7·103 Posts
Default 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:
Click image for larger version

Name:	numberline.png
Views:	65
Size:	3.6 KB
ID:	15059
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.
Click image for larger version

Name:	spiral.png
Views:	68
Size:	8.7 KB
ID:	15060
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<y\), there exists \(q\in\mathbb{Q}\) such that \(x<q<y\)
("there is a rational number between any 2 distinct real numbers").

24. Show that, for all non-zero integers \(m\) and \(n\), the real number \(\frac{m}{n}\sqrt{2}\) is irrational. Deduce that, for all \(q,r\in\mathbb{Q}\) with \(q<r\), there exists \(x\in\mathbb{R}\setminus\mathbb{Q}\) such that \(q<x<r\)
("there is an irrational number between any 2 distinct rational numbers").

25. Find all units in the integers modulo 10.

26. Calculate the inverse of \(\overline{829}\) in the integers modulo 4567 without using a computer.
Nick is online now   Reply With Quote
Old 2016-10-21, 22:21   #2
chalsall
If I May
 
chalsall's Avatar
 
"Chris Halsall"
Sep 2002
Barbados

2·4,657 Posts
Default

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.
chalsall is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Basic Number Theory 1 & 2 Nick Number Theory Discussion Group 17 2017-12-23 20:10
Basic Number Theory 20: polynomials Nick Number Theory Discussion Group 5 2017-04-25 14:32
Basic Number Theory 16: unit group structure in modular arithmetic Nick Number Theory Discussion Group 0 2017-01-19 20:22
Basic Number Theory 15: Lagrange's theorem, cyclic groups and modular arithmetic Nick Number Theory Discussion Group 0 2017-01-07 13:15
Basic Number Theory 14: a first look at groups Nick Number Theory Discussion Group 0 2016-12-29 13:47

All times are UTC. The time now is 22:17.

Wed Sep 30 22:17:08 UTC 2020 up 20 days, 19:28, 0 users, load averages: 1.25, 1.47, 1.49

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.