20160924, 22:16  #1  
Dec 2012
The Netherlands
2·3·307 Posts 
Basic Number Theory 1 & 2
Quote:
In some (mainly older) books, they prefer to start at 1. We use the symbol \(\mathbb{N}\) for the set of all natural numbers. The notation \(x\in\mathbb{N}\) means that \(x\) is an element of the set \(\mathbb{N}\), i.e. \(x\) is a natural number. The notation \(x\notin\mathbb{N}\) means \(x\) is not an element of the set \(\mathbb{N}\). Thus, for example, we may say \(1\in\mathbb{N}\) but \(1\notin\mathbb{N}\). If \(x\in\mathbb{N}\) and \(y\in\mathbb{N}\) then we also have \(x+y\in\mathbb{N}\). We express this by saying that the set \(\mathbb{N}\) is closed under addition. Similarly, \(\mathbb{N}\) is closed under multiplication, but not under subtraction. For example, \(1\in\mathbb{N}\) and \(2\in\mathbb{N}\) but \(12\notin\mathbb{N}\). The integers are all the whole numbers ...,5,4,3,2,1,0,1,2,3,4,5,... We write \(\mathbb{Z}\) for the set of all integers (this comes from the German word for number: "Zahl"). Every element of the set \(\mathbb{N}\) is also an element of the set \(\mathbb{Z}\) (every natural number is an integer). We express this by saying that \(\mathbb{N}\) is a subset of \(\mathbb{Z}\) and writing \(\mathbb{N}\subset\mathbb{Z}\). If \(x\in\mathbb{Z}\) then we also have \(x\in\mathbb{Z}\), so we say that the set \(\mathbb{Z}\) is symmetric. \(\mathbb{Z}\) is closed under addition, subtraction and multiplication, but not under division. For any sets \(A\) and \(B\), we write \(A\cap B\) for the intersection of \(A\) and \(B\), i.e. the set of all elements contained in both \(A\) and \(B\). We write \(A\cup B\) for the union of \(A\) and \(B\), which is the set of all elements contained in \(A\) or in \(B\) (or both). For example, if \(A\) is the set of all even integers and \(B\) the set of all positive integers, then \(A\cap B\) is the set of all integers that are both even and positive, while \(A\cup B\) is the set of all integers which are even or positive (including the even positive integers). It follows directly from these definitions that \(A\cap B\) is a subset both of \(A\) and of \(B\) while \(A\) and \(B\) are each subsets of \(A\cup B\). Proposition Let \(A\) and \(B\) be sets of numbers, each closed under addition. Then the set \(A\cap B\) is also closed under addition. proof Take any elements \(x,y\in A\cap B\). Then \(x\in A\) and \(y\in A\) and \(A\) is closed under addition so \(x+y\in A\). Similarly, \(x+y\in B\) hence \(x+y\in A\cap B\). ∎ Exercises 1. Show that we cannot replace intersection with union in the above proposition. In other words, find 2 sets of numbers \(A\) and \(B\) each closed under addition for which the union \(A\cup B\) is not closed under addition. 2. Let \(S\) be a finite set of numbers. Suppose that the number of elements in \(S\) is odd and that \(S\) is symmetric. Deduce that \(0\in S\). 3. Find a set of numbers with as few elements as possible which contains the numbers 12 and 30 and is closed under subtraction. 4. If a set of numbers is closed under addition and is symmetric, then it is also closed under subtraction (since \(xy=x+(y)\) for any numbers \(x\) and \(y\)). Show that the converse also holds, i.e. if a set of numbers is closed under subtraction then it is also symmetric and closed under addition. 

20160930, 18:14  #2 
Dec 2012
The Netherlands
732_{16} Posts 
For any integers \(a\) and \(b\), we say \(a\) divides \(b\) and write \(ab\) if there exists an integer \(n\) such that \(an=b\).
Instead of saying \(a\) divides \(b\), we may call \(a\) a divisor or factor of \(b\), or say that \(b\) is a multiple of \(a\). Some people also require \(n\) in the above definition to be unique. The only difference is that the statement "0 divides 0" is not true under their definition, but it is true under ours. Examples \(220\), \(220\), \(11111234321\). For any integer \(n\), \(1n\) and \(nn\). Proposition 1 For any integers \(a\) and \(b\) with \(b>0\), if \(a\) divides \(b\) then \(a\leq b\). proof If \(a\leq 0\) then, as \(b>0\), we have \(a\leq b\) immediately. Suppose instead that \(a>0\) and \(a\) divides \(b\). Then \(an=b\) for some integer \(n\), and \(a\) and \(b\) are both positive so \(n>0\) too. As \(n\) is an integer, it follows that \(n\geq 1\) hence \(b=an\geq a\). ∎ Proposition 2 For any natural numbers \(a\) and \(b\), if \(ab\) and \(ba\) then \(a=b\). proof If \(a=0\) and \(ab\) then \(b=0\) so \(a=b\). Similarly, if \(b=0\) and \(ba\) then \(a=0=b\). Otherwise, as \(a\) and \(b\) are natural numbers, they are both positive, so if \(ab\) then \(a\leq b\) by proposition 1, and similarly if \(ba\) as well then \(b\leq a\) too, hence \(a=b\). ∎ For any integer \(d\), the set of all multiples of \(d\) is denoted by \(d\mathbb{Z}\) or simply \((d)\). Example \(2\mathbb{Z}\), or simply \((2)\), is the set of all even numbers. In mathematical notation, there are 3 commonly used ways to specify a set. One way is simply to list all its elements, which we do between curly brackets: \[ 2\mathbb{Z}=\{\ldots,8,6,4,2,0,2,4,6,8,\ldots\}. \] Another way is to give a formula and the set of values each variable involved may take. Here we could write \[ 2\mathbb{Z}=\{2n:n\in\mathbb{Z}\} \] Read this as: "\(2\mathbb{Z}\) is the set of everything expressible in the form \(2n\) where \(n\) is an element of \(\mathbb{Z}\)". A third way is to select the elements of a larger set which have a particular property. In this example, we could put \[ 2\mathbb{Z}=\{n\in\mathbb{Z}:2\mbox{ divides } n\} \] Read this as: "\(2\mathbb{Z}\) is the set of all elements \(n\) in \(\mathbb{Z}\) such that \(2\) divides \(n\)". (Some people prefer to use a vertical bar instead of the colon in the above notation, but the meaning is the same.) Take any integer \(n\). If \(n\) is an element of the set \(2\mathbb{Z}\) then \(2\) divides \(n\). In mathematical notation, we can write this quite simply as: \[ n\in 2\mathbb{Z}\Rightarrow 2n. \] Conversely, if \(2\) divides \(n\) then \(n\) is an element of \(2\mathbb{Z}\), so \(n\) is in \(2\mathbb{Z}\) if and only if \(2\) divides \(n\). We write this as: \[ n\in 2\mathbb{Z}\Leftrightarrow 2n. \] The statements on the left and on the right of the symbol "\(\Leftrightarrow\)" are either both true, or both not true. Proposition 3 For any integer \(d\), \(0\) is an element of \(d\mathbb{Z}\) and \(d\mathbb{Z}\) is closed under subtraction. proof We have \(0=d\cdot 0\in d\mathbb{Z}\). For any \(a,b\in d\mathbb{Z}\), there exist integers \(m\) and \(n\) such that \(a=dn\) and \(b=dm\). So \(ab=d(nm)\) and \(nm\) is also an integer, hence \(ab\in d\mathbb{Z}\). ∎ Proposition 4 Let \(d\) be an integer and \(S\) a set of integers closed under subtraction with \(d\in S\). Then \(d\mathbb{Z}\subset S\). proof As \(S\) is closed under subtraction, it is also symmetric and closed under addition (see exercise 4). We must prove for all integers \(n\) that \(dn\in S\). Consider first the case \(n=0\). We have \(d\in S\) and \(S\) is closed under subtraction so \(dn=0=dd\in S\). Now suppose we have shown that \(dn\in S\) for all nonnegative integers \(n\) less than some positive integer \(N\), and consider the case \(n=N\). By our assumption, we have \(d(n1)\in S\). Also, \(d\in S\) and \(S\) is closed under addition, so \(dn=d(n1)+d\in S\). It follows by induction that \(dn\in S\) for all integers \(n\geq 0\). (Informally, we have shown the statement is true for n=0, and that if it is true with n=0 then it is true with n=1, and that if it is true with n=1 then it is true with n=2, etc.) Now take any integer \(n<0\). Then \(n>0\) so, by what we have already proved, \(d(n)\in S\). And \(S\) is symmetric hence \(dn=d(n)\in S\). ∎ Next, let us look at division with remainders. Proposition 5 Let \(a\) and \(b\) be integers with \(b>0\). Then there exist unique integers \(q\) and \(r\) such that \(a=qb+r\) and \(0\leq r<b\). proof EXISTENCE We shall use induction on \(a\). In the case \(a=0\), we can simply use the values \(q=0\) and \(r=0\). Take any positive integer \(N\) and suppose we have shown that integers \(q\) and \(r\) with the given properties exist in all cases where \(a<N\). We now consider the case \(a=N\) itself. By our assumption, there exist integers \(q'\) and \(r'\) such that \(a1=q'b+r'\) with \(0\leq r'<b\). If \(r'<b1\) then, putting \(q=q'\) and \(r=r'+1\), we get \(a=qb+r\) with \(0\leq r<b\) as required. Otherwise, \(r'=b1\) so, letting \(q=q'+1\) and \(r=0\), we get \(a=q'b+r'+1=(q'+1)b+0=qb+r\) with \(r=0<b\), again as required. It follows by induction that integers \(q\) and \(r\) with the given properties exist in all cases where \(a\geq 0\). Now take any integer \(a<0\). Then \(a>0\) so, by what we have proved already, there exist integers \(q'\) and \(r'\) such that \(a=q'b+r'\) with \(0\leq r'<b\). If \(r'=0\) then we can simply use the values \(q=q'\) and \(r=r'\). Otherwise, we have \(0<r'<b\) so, putting \(q=q'1\) and \(r=br'\), we get \(a=q'br'=(q'1)b+br'=qb+r\) with \(0<r<b\). UNIQUENESS Take any integers \(q,q',r,r'\) and suppose \(a=qb+r\) with \(0\leq r<b\) and also \(a=q'b+r'\) with \(0\leq r'<b\). Then \(b<r'r<b\) and \((qq')b=r'r\) so \(1<qq'<1\). But \(qq'\) is an integer, hence \(qq'=0\) giving \(q=q'\) and therefore \(r=r'\). ∎ The above proposition may not look particularly special, but in fact it is crucial, underpinning many important theorems about the integers. We can use it immediately to prove that, remarkably, the converse of proposition 3 also holds. Proposition 6 Let \(S\) be a set of integers closed under subtraction with \(0\in S\). Then there exists a unique \(d\in\mathbb{N}\) such that \(S=d\mathbb{Z}\). proof EXISTENCE As \(S\) is closed under subtraction, it is also symmetric and closed under addition (see exercise 4). If 0 is the only element of \(S\) then \(S=0\mathbb{Z}\). Otherwise \(S\) contains at least one nonzero integer and, since \(S\) is symmetric, it contains at least one positive integer. Let \(d\) be the smallest positive integer in \(S\). By proposition 4, we have \(d\mathbb{Z}\subset S\). Conversely, for any integer \(a\in S\) there exist integers \(q\) and \(r\) such that \(a=qd+r\) with \(0\leq r<d\) by proposition 5. Now \(qd\) is an element of \(d\mathbb{Z}\) which is a subset of \(S\) so \(qd\in S\). We also have \(a\in S\) and \(S\) is closed under subtraction, hence \(r=aqd\in S\). But \(r<d\) and \(d\) is the smallest positive integer in \(S\) so \(r=0\) and therefore \(a=qd\in d\mathbb{Z}\). This holds for all \(a\in S\) so \(S\subset d\mathbb{Z}\). We have proved that \(d\mathbb{Z}\subset S\) and that \(S\subset d\mathbb{Z}\), so the sets \(S\) and \(d\mathbb{Z}\) have precisely the same elements, making them equal. UNIQUENESS For any natural numbers \(c\) and \(d\), if \(c\mathbb{Z}=d\mathbb{Z}\) then \(c\in d\mathbb{Z}\) so \(dc\) and \(d\in c\mathbb{Z}\) so \(cd\), hence \(c=d\) by proposition 2. ∎ Exercises 5. Show that, for any integers \(a\), \(b\) and \(c\), if \(a\) divides \(b\) and \(b\) divides \(c\) then \(a\) divides \(c\). 6. Show that, for any integers \(a\) and \(b\), \( b\mathbb{Z}\subset a\mathbb{Z}\Leftrightarrow ab\). 7. Determine \(\{n\in\mathbb{Z}:n1\}\). 8. Prove by induction that, for any positive integer \(n\), \( 1+2+3+\ldots +n=\frac{n(n+1)}{2}\). 9. The set \(12\mathbb{Z}\cap 30\mathbb{Z}\) is closed under subtraction and contains 0 so, by proposition 6, \(12\mathbb{Z}\cap 30\mathbb{Z}=m\mathbb{Z}\) for some unique integer \(m\geq 0\). What is the value of \(m\)? 10. Which of the following statements are true and which are false? i) \(10\); ii) \((1)=\mathbb{Z}\); iii) \((0)=\{0\}\); iv) for any integer \(n\), \(n<2\Rightarrow n^2<4\); v)\( \{n\in\mathbb{Z}: 8n^21\}=\{2m+1:m\in\mathbb{Z}\}\). 
20160930, 22:50  #3 
Just call me Henry
"David"
Sep 2007
Liverpool (GMT/BST)
1849_{16} Posts 
I had meant to come back to this and do the exercises. I suppose now is my chance.
1) Let [$]\mathbb{A}=\{2x, x\in\mathbb{Z}\}[/$] and [$]\mathbb{B}=\{3x, x\in\mathbb{Z}\}[/$]. These are both closed under addition. [$]2,3\in\mathbb{A}\cup\mathbb{B}[/$] and [$]2+3=5\notin\mathbb{A}\cup\mathbb{B}[/$]. 2) We start with a symmetric set A with n elements.n is odd. Since the set is symmetric if x is in the set x is also in the set. We can consider a subset of A where each pair of numbers x and x has been removed x > 0. Since we are removing both x and x symmetry is maintained. We are now left with one element in this subset of A which we will call B. Since B is symmetric, x and x must both be in B. If there is only one element x must equal x. This can only be true if x=0. 3) Given that only infinite sets have been defined in this strictly speaking this is impossible using the information provided. A modular set could be used but this hasn't been defined yet. With what has been defined so far the set [$]\mathbb{A}=\{12+18x, x\in\mathbb{Z}\}[/$] fits the question. 4) If a set [$]\mathbb{A}[/$] is closed under subtraction and [$]x \in \mathbb{A}[/$], then [$]xx=0 \in \mathbb{A}[/$]. Also [$]0x=x \in \mathbb{A}[/$]. This means that if [$]x \in \mathbb{A}[/$], [$]x \in \mathbb{A}[/$] or in other words [$]\mathbb{A}[/$] is symmetric. For [$]x,y \in \mathbb{A}[/$], [$]xy \in \mathbb{A}[/$]. Since [$]\mathbb{A}[/$] is symmetric [$]y \in \mathbb{A}[/$]. Since [$]xy=x+(y)[/$], [$]\mathbb{A}[/$] must be closed under addition. Please feel free to criticise the proofs more harshly than you would someone without formal training in maths. I have done a maths BSc. Any constructive criticism would be appreciated. I am a little rusty. The next set of exercises will follow eventually. I am enjoying reading this. Last fiddled with by henryzz on 20160930 at 22:51 
20161001, 02:47  #4  
Romulan Interpreter
"name field"
Jun 2011
Thailand
2876_{16} Posts 
Quote:
Edit: PS: the proof for proposition 2 is wrong: it is not underlined Last fiddled with by LaurV on 20161001 at 02:53 

20161001, 02:56  #5 
Aug 2006
1011101100100_{2} Posts 

20161001, 10:09  #6 
Just call me Henry
"David"
Sep 2007
Liverpool (GMT/BST)
6,217 Posts 
Ok. I see that my answer for 3) was wrong. I don't see how you get that 6 was in my set. I thought just 6 was. Of course it should be symmetric as proved in 4). [$]\mathbb{A}=\{6xx\in\mathbb{Z}\}[/$] is the best answer I can come up with.

20161001, 18:45  #7 
Aug 2006
2^{2}·3·499 Posts 

20161001, 19:09  #8  
"Forget I exist"
Jul 2009
Dartmouth NS
5·13·131 Posts 
Quote:


20161001, 19:10  #9 
"Robert Gerbicz"
Oct 2005
Hungary
2·3·5^{2}·11 Posts 

20161001, 19:48  #10 
Aug 2006
2^{2}·3·499 Posts 

20161003, 10:16  #11 
Romulan Interpreter
"name field"
Jun 2011
Thailand
2×5,179 Posts 
I think this should be a SUBForum, not just a thread. Nick, can you do this with your current rights? If not, a supermod, please, create a subforum, put Nick's posts in it as threads. Like, chapter 1, chapter 2, etc (of course, they don't need to be called so, I only gave an example, but the order, 1, 2, 3, etc, is a must). Then Nick, if you want to continue, please post a new thread every time in that subforum. And we can argue about exercises, (and CRG can take my examples in post #4 and give them in post #7 as they are his ( just kidding buddy, hehe)), in each "that particular" thread.
Otherwise, if we put "all in one thread", Nick's interesting theory stuff gets mixed deepdeep inside discussions and arguments, and me sticking the tongue out to you, and etc, therefore difficult to find and read. We must have each of Nick's post as a starting of a new thread. In a SubForum. It is a tremendous amount of work what he does, for us, and for free. Like chapters of a book, with exercises for each chapter, etc, we must keep them separate, not mix together. Maybe the current can stay together, as Nicks posts are the first two. But from now on, please Nick, do not post at the end of the current thread, but create a new one. Last fiddled with by LaurV on 20161003 at 10:39 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Basic Number Theory 21: ideals and homomorphisms  Nick  Number Theory Discussion Group  5  20170604 12:36 
Basic Number Theory 20: polynomials  Nick  Number Theory Discussion Group  5  20170425 14:32 
Basic Number Theory 17: quadratic reciprocity  Nick  Number Theory Discussion Group  0  20170131 14:41 
Basic Number Theory 14: a first look at groups  Nick  Number Theory Discussion Group  0  20161229 13:47 
Basic Number Theory 12: sums of two squares  Nick  Number Theory Discussion Group  0  20161211 11:30 