Basic Number Theory 1 & 2

Nick · 2016-09-24, 22:16

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.

Nick · 2016-09-30, 18:14

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 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 $a-1=q'b+r'$ with $0\leq r'<b$. If $r'<b-1$ then, putting $q=q'$ and $r=r'+1$, we get $a=qb+r$ with $0\leq r<b$ as required.
Otherwise, $r'=b-1$ 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=b-r'$, we get $a=-q'b-r'=(-q'-1)b+b-r'=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 $(q-q')b=r'-r$ so $-1<q-q'<1$.
But $q-q'$ is an integer, hence $q-q'=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 non-zero 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=a-qd\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 $d|c$ and $d\in c\mathbb{Z}$ so $c|d$, 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 a|b$.

7. Determine $\{n\in\mathbb{Z}:n|1\}$.

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) $1|0$;
ii) $(1)=\mathbb{Z}$;
iii) $(0)=\{0\}$;
iv) for any integer $n$, $n<2\Rightarrow n^2<4$;
v)$ \{n\in\mathbb{Z}: 8|n^2-1\}=\{2m+1:m\in\mathbb{Z}\}$.

henryzz · 2016-09-30, 22:50

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.

LaurV · 2016-10-01, 02:47

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

CRGreathouse · 2016-10-01, 02:56

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.

henryzz · 2016-10-01, 10:09

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.

CRGreathouse · 2016-10-01, 18:45

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.

science_man_88 · 2016-10-01, 19:09

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)

R. Gerbicz · 2016-10-01, 19:10

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.

CRGreathouse · 2016-10-01, 19:48

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.

LaurV · 2016-10-03, 10:16

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.

2016-09-30, 18:14	#2
Nick Dec 2012 The Netherlands 732₁₆ 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 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 \(a-1=q'b+r'\) with \(0\leq r'<b\). If \(r'<b-1\) then, putting \(q=q'\) and \(r=r'+1\), we get \(a=qb+r\) with \(0\leq r<b\) as required. Otherwise, \(r'=b-1\) 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=b-r'\), we get \(a=-q'b-r'=(-q'-1)b+b-r'=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 \((q-q')b=r'-r\) so \(-1<q-q'<1\). But \(q-q'\) is an integer, hence \(q-q'=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 non-zero 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=a-qd\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 \(d\|c\) and \(d\in c\mathbb{Z}\) so \(c\|d\), 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 a\|b\). 7. Determine \(\{n\in\mathbb{Z}:n\|1\}\). 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) \(1\|0\); ii) \((1)=\mathbb{Z}\); iii) \((0)=\{0\}\); iv) for any integer \(n\), \(n<2\Rightarrow n^2<4\); v)\( \{n\in\mathbb{Z}: 8\|n^2-1\}=\{2m+1:m\in\mathbb{Z}\}\).

2016-09-30, 22:50	#3
henryzz Just call me Henry "David" Sep 2007 Liverpool (GMT/BST) 1849₁₆ 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-03, 10:16	#11
LaurV Romulan Interpreter "name field" Jun 2011 Thailand 2×5,179 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
Basic Number Theory 21: ideals and homomorphisms	Nick	Number Theory Discussion Group	5	2017-06-04 12:36
Basic Number Theory 20: polynomials	Nick	Number Theory Discussion Group	5	2017-04-25 14:32
Basic Number Theory 17: quadratic reciprocity	Nick	Number Theory Discussion Group	0	2017-01-31 14:41
Basic Number Theory 14: a first look at groups	Nick	Number Theory Discussion Group	0	2016-12-29 13:47
Basic Number Theory 12: sums of two squares	Nick	Number Theory Discussion Group	0	2016-12-11 11:30

2016-10-01, 10:09	#6
henryzz 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}=\{6x\|x\in\mathbb{Z}\}[/$] is the best answer I can come up with.