mersenneforum.org > Math Basic Number Theory 1 & 2
 Register FAQ Search Today's Posts Mark Forums Read

2016-09-24, 22:16   #1
Nick

Dec 2012
The Netherlands

110111001012 Posts
Basic Number Theory 1 & 2

Quote:
 And I will begin that tale, though others shall end it.
The natural numbers are the numbers 0,1,2,3,4,5,...

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 $$1-2\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 $$x-y=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.

 2016-09-30, 18:14 #2 Nick     Dec 2012 The Netherlands 5×353 Posts For any integers $$a$$ and $$b$$, we say $$a$$ divides $$b$$ and write $$a|b$$ 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 $$2|20$$, $$-2|20$$, $$1111|1234321$$. For any integer $$n$$, $$1|n$$ and $$n|n$$. 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 $$a|b$$ and $$b|a$$ then $$a=b$$. proof If $$a=0$$ and $$a|b$$ then $$b=0$$ so $$a=b$$. Similarly, if $$b=0$$ and $$b|a$$ then $$a=0=b$$. Otherwise, as $$a$$ and $$b$$ are natural numbers, they are both positive, so if $$a|b$$ then $$a\leq b$$ by proposition 1, and similarly if $$b|a$$ 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 2|n.$ 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 2|n.$ 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 $$a-b=d(n-m)$$ and $$n-m$$ is also an integer, hence $$a-b\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=d-d\in S$$. Now suppose we have shown that $$dn\in S$$ for all non-negative integers $$n$$ less than some positive integer $$N$$, and consider the case $$n=N$$. By our assumption, we have $$d(n-1)\in S$$. Also, $$d\in S$$ and $$S$$ is closed under addition, so $$dn=d(n-1)+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 r0$$ so, by what we have proved already, there exist integers $$q'$$ and $$r'$$ such that $$-a=q'b+r'$$ with $$0\leq r'  2016-09-30, 22:50 #3 henryzz Just call me Henry "David" Sep 2007 Liverpool (GMT/BST) 23×7×107 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 []x-x=0 \in \mathbb{A}[/]. Also []0-x=-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}[/], []x-y \in \mathbb{A}[/]. Since []\mathbb{A}[/] is symmetric []-y \in \mathbb{A}[/]. Since []x-y=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 2016-09-30 at 22:51 2016-10-01, 02:47 #4 LaurV Romulan Interpreter "name field" Jun 2011 Thailand 100111000111112 Posts Quote:  Originally Posted by henryzz 3)With what has been defined so far the set []\mathbb{A}=\{12+18x, x\in\mathbb{Z}\}[/] fits the question. Errr... no... with modular sets you have the set {0 (mod 6)}, without you have {6x: x in Z}. That is because 30-12=18, 18-12=6, so 6 is in your set, therefore all its multiples Edit: PS: the proof for proposition 2 is wrong: it is not underlined Last fiddled with by LaurV on 2016-10-01 at 02:53 2016-10-01, 02:56 #5 CRGreathouse Aug 2006 5,981 Posts Quote:  Originally Posted by LaurV therefore all its multiples In case this isn't clear: 6 is in the set, so 6 - 6 = 0 is in the set, as is 0 - 6 = -6, and so for any x in the set, x - 6 and x - (-6) = x + 6 are in the set.  2016-10-01, 10:09 #6 henryzz Just call me Henry "David" Sep 2007 Liverpool (GMT/BST) 23×7×107 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}=\{6x|x\in\mathbb{Z}\}[/] is the best answer I can come up with. 2016-10-01, 18:45 #7 CRGreathouse Aug 2006 598110 Posts Quote:  Originally Posted by henryzz I don't see how you get that 6 was in my set. 30 and 12 are in the set, so 30 - 12 = 18 and 18 - 12 = 6 are also in the set. 2016-10-01, 19:09 #8 science_man_88 "Forget I exist" Jul 2009 Dumbassville 3×2,797 Posts Quote:  Originally Posted by henryzz 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}=\{6x|x\in\mathbb{Z}\}[/] is the best answer I can come up with. here's my easiest explanation I actually PM'd nick when the thread started with my answers to the first few exercises given. think about gcd , gcd(12,30)==6 so that we can create all the multiples of 6 ( positive and negative) and that doesn't need all numbers as gcd(12/6,30/6)==gcd(2,5)==1 we get that it has to be symmetric because if a==b then it implies a-b =0 other wise both a-b and b-a have to be in the set one is the negative of the other ( proof is simple if you allow rearrangement start with the facts that subtraction is the addition of a negative value and multiplying by a negative reverses signs , -(a-b) == (-1)*a-(-1)*b == -a+b == b-a) and again as gcd(2,5)==1 we get for free their difference multiplied by 6 ( aka the subtraction being done) will not share any other factors, if they did have gcd>1 then it would be only multiples of 6 sharing those factors and would continue likewise down) 2016-10-01, 19:10 #9 R. Gerbicz "Robert Gerbicz" Oct 2005 Hungary 30458 Posts Quote:  Originally Posted by CRGreathouse 30 and 12 are in the set, so 30 - 12 = 18 and 18 - 12 = 6 are also in the set. This problem is similar to p9, and in general \(aZ\cap bZ$$ =gZ for g=gcd(a,b), and here gcd(12,30)=6.

2016-10-01, 19:48   #10
CRGreathouse

Aug 2006

5,981 Posts

Quote:
 Originally Posted by R. Gerbicz This problem is similar to p9, and in general $$aZ\cap bZ$$ =gZ for g=gcd(a,b), and here gcd(12,30)=6.
Yes. That's what I saw, and I worked backward from there to as simple an explanation as I could find for it.

 2016-10-03, 10:16 #11 LaurV Romulan Interpreter     "name field" Jun 2011 Thailand 5·2,003 Posts I think this should be a SUB-Forum, not just a thread. Nick, can you do this with your current rights? If not, a supermod, please, create a sub-forum, 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 sub-forum. 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 deep-deep 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 Sub-Forum. 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 2016-10-03 at 10:39

 Similar Threads Thread Thread Starter Forum Replies Last Post Nick Number Theory Discussion Group 5 2017-06-04 12:36 Nick Number Theory Discussion Group 5 2017-04-25 14:32 Nick Number Theory Discussion Group 0 2017-01-31 14:41 Nick Number Theory Discussion Group 0 2016-12-29 13:47 Nick Number Theory Discussion Group 0 2016-12-11 11:30

All times are UTC. The time now is 14:13.

Wed Aug 17 14:13:20 UTC 2022 up 41 days, 9 hrs, 1 user, load averages: 1.25, 1.67, 1.66