Elementary Number Theory
Elementary
Number Theory
The
well-ordering Principle
- Every
nonempty set of positive integers has a least element
1) Proof
that:
$\forall
a,b \in \mathbb{Z^{+}}, \exists n\in \mathbb{Z^{+}}$ such that $na>b$
Solution:
We prove
this by contradiction. Assume the statement is wrong, then we have $\exists a,b$
such that $na \le b, \forall n\in \mathbb{Z^{+}}$
$$na \le
b$$
$$b-na
\ge 0$$
Define:
$$T=\{b-ma:m
\in \mathbb{Z^{+}}\}$$
Since $a,b\in
\mathbb{Z^{+}}$ and $m \in \mathbb{Z^{+}}$, then $b-ma \in \mathbb{Z^{+}}$
Hence, $T$
is a set of positive integers
Clearly,
$$b-na
\in T$$
$T$ is a
set of non-zero positive integers. Thus, by well-ordering principle, we should
able to find a least element, say $b-xa \in T$
Consider
another element in $T$:
$$b-(x+1)a
\in T$$
And,
$$b-(x+1)a
= b-xa-a = (b-xa)-a$$
But,
$$(b-xa)-a
< b-xa$$
We
obtain a conclusion that says $b-(x+1)a \in T$ which is smaller than the least
element $b-xa \in T$
This
contradict with the well-ordering principle
$\therefore$
Our assumption is wrong which mean that the statement is true
$\therefore$
$\forall a,b \in \mathbb{Z^{+}}, \exists n\in \mathbb{Z^{+}}$ such that $na>b$
2) Proof that:
$\sqrt{2}$
is irrational
Solution:
Prove by
contradiction. Assume the statement is wrong, then we have $\sqrt{2}$ is
irrational.
$$\sqrt{2}
=\frac{a}{b}, a,b \in \mathbb{Z^{+}}$$
$$a=b\sqrt{2}
\in \mathbb{Z^{+}}$$
Define:
$$T=\{x\sqrt{2}:x
\in \mathbb{Z^{+}}\}$$
$$\text{Let }
y=x\sqrt{2} \in T$$
$$y \in
T$$
Thus, $T$
is a set of positive integers
Futhermore,
$$a=b\sqrt{2}
\in T$$
$\therefore
T$ is a non-zero set
By
well-ordering principle, $T$ has a least element which we called $s=t\sqrt{2}
\in T$
Next, we
construct another element in $T$
$$s\sqrt{2}-s$$
$\color{yellow}{\text{*
we need to check that whether $s\sqrt{2}-s$ is in $T$}}$
1.$s\sqrt{2}-s
= s\sqrt{2}-t\sqrt{2} = (s-t)\sqrt{2}$
$\Rightarrow$
This is in the form of element in $T$
2.$s\sqrt{2}-s
= s(\sqrt{2}-1) > 0$
$\Rightarrow
s\sqrt{2}-s$ is positive
$\therefore$
From 1. and 2. we can show that $s\sqrt{2}-s \in T$
But,
$$s\sqrt{2}-s
= t\sqrt{2}\sqrt{2}-t\sqrt{2} = t(2-\sqrt{2})$$
$$t(2-\sqrt{2})
< t\sqrt{2} =s$$
$\therefore$
We obtain another element in $T$ less than the least element. Thus, we obtain a
contradiction. Our assumption is wrong
$\therefore$
$\sqrt{2}$ is irrational
3) Proof that:
Let $S$
be a set of positive integers with the following properties:
(a) The
integer $1$ belongs to $S$
(b)
Whenever he integer $k$ is in $S$, the next integer $k+1$ must also be in $S$.
Then $S$
is the set of all positive integers.
Solution:
Define
the following set:
$$T=\mathbb{Z^{+}}\backslash
S$$
1. $T =
\mathbb{Z^{+}} \backslash S \subseteq \mathbb{Z^{+}}$
$\therefore$
$T$ is also a set of positive integers
2. if $T
= \{\text{ }\}$, then
$$\{\text{ }\} = \mathbb{Z^{+}} \backslash S$$
$\therefore
S=\mathbb{Z^{+}}$
On the
other hand, if $T \neq \{\text{ }\}$,
then by the well-ordering principle, $T$ has a least element
Let the
least element in $T$ to be $“a”$
Given
(a) $1 \in S$
Then $a
> 1$, thus $a-1 > 0$ which implies $a-1 \in \mathbb{Z^{+}}$
Since
$a$ is smallest in $T$ and $a-1<a$, then $a-1 \in S$
From (b)
Since
$a-1 \in S$, then $(a-1)+1 \in S$
Which
mean $a \in S$
Therefore,
$a \in S \bigcap T$ which contradicts $T=\mathbb{Z^{+}}\backslash S$
Thus,
$T=\{\text{ }\}$ and so
$S=\mathbb{Z^{+}}$
4) Proof that:
Suppose
$a,b,c \in \mathbb{Z^{+}}$, $a|b$ and $b|c \Rightarrow a|c$
Solution:
$$a|b :
b=ma,n \in \mathbb{Z}$$
$$b|c :
c=mb,m \in \mathbb{Z}$$
$$c=m(na)
= (mn)a,\text{for some } mn \in \mathbb{Z}$$
$\therefore
a|c$
5) Proof that:
Suppose
$a,b,m,n \in \mathbb{Z}$, $c|a$ and $c|b \Rightarrow c|(ma+nb)$
Solution:
$$c|a :
a=ck_{1},k_{1} \in \mathbb{Z}$$
$$c|b :
b=ck_{2},k_{2} \in \mathbb{Z}$$
$$ma+nb
= cmk_{1} + nck_{2} = c(mk_{1}+nk_{2}), mk_{1}+nk_{2} \in \mathbb{Z}$$
$\therefore
c|b \Rightarrow c|(ma+nb)$
6) Proof that:
Suppose
$a,b \in \mathbb{Z},b>0$. Then there exists unique $q,r \in \mathbb{Z}$ such
that $a=bq+r$ with $0 \le r < b$
Solution:
We need
to perform the following:
i)
obtain the formula $a=bq+r$
ii) show
that $r \ge 0$
iii)
show that $r<b$
iv) show
that $q$ and $r$ are unique
Define:
$$S=\{a-bx
: a-bx \ge 0, x \in \mathbb{Z}\}$$
To use
the well-ordering principle on S, we need to show that S is non-empty
$$b>0$$
$$b \ge
1$$
$$|a|b\ge
|a$$
From the
set $S$, we have
$$a-b(-|a|)
= a+b|a| = a +|a|b$$
$$a+|a|b
\ge a +|a|$$
Since $a+|a|\begin{cases}a+a,&\text{if
$a \ge 0$}\\ a-a,&\text{if $a<0$}\end{cases}$
$\therefore$
it is always greater than $0$ because $a+|a| \ge 0$
$\therefore
a-b(-|a|)$ is in the form exactly as the form element in $S$
Furthermore,
$a-b(-|a|) \ge 0$
$\therefore
a-b(-|a|) \in S\neq\{\text{ }\}$
Since $ S\neq\{\text{ }\}$, then by well-ordering principle, there
is a least element in $S$, say $a-bq = r$
Since $a-bq$
is inside $S$, therefore $r\ge 0$
$\color{yellow}{\text{Next,
we need to show $r<b$}}$
Prove by
contradiction. Assume $r \ge b$
Consider,
another element is $S$, say $a-b(q+1)$
$a-b(q+1)
= a-bq-b = r – b \ge 0$(from the assumption that $r \ge b$ $\Rightarrow$ $r-b \ge
0$)
$\therefore
a-b(q+1) \in S$
But,
$$ a-b(q+1)
= a-bq-b=r-b \le r = a-bq$$(least
element)
$\therefore$
We obtain a contradiction. Thus, the assumption is wrong
$\therefore
r<b$
Constructed,
$r=a-bq$
$a=bq+r,
0\le r < b$
$\color{yellow}{\text{we
need to show $q,r$ are unique}}$
Assume
(1) $a=bq+r$,
$0 \le r < b$(3) and
(2) $a=bq’+r’$,
$0 \le r’ < b$(4)
Which means
we have two different representation for the division algorithm
(1) - (2):
$$0=b(q-q’)
+ (r-r’)$$
$$b(q-q’)=r’-r$$
(3):
$$0 \le
r < b$$
$$-b
< -r \le 0$$
(4): $$0
\le r’ < b$$
(3) + (4):
$$-b
< r’-r <b$$
$$|r’-r|
< b$$
$$|b(q-q’)|
= |r’-r|$$
$$b|q-q’|=|r’-r| \text{------(5)}$$
$$b|q-q’|<b$$
from (3) + (4)
$$0 \le
|q-q’| < 1$$
Since $q
\in \mathbb{Z}$, $q’ \in \mathbb{Z}$ $\Rightarrow q-q’$ must be $\mathbb{Z}$
$\therefore
|q-q’|=0$
$$\Rightarrow
q = q’$$
(5):
$$b(0) =
|r’-r|$$
$$0=|r’-r|$$
$$r=r’$$
$\therefore$
$q$ and $r$ is unique.
7) Proof that:
Every
positive integer greater than $1$ has a prime divisor
Solution:
We prove
by contradiction, assume the statement is false then there exists a positive
integer greater than $1$ does not have a prime divisor.
Define a
set $S$ as follows:
S = the
set consists of all positive integer greater than $1$ with no prime divisor
=$\{x \in \mathbb{Z^{+}},x>1, x \text{
with no prime divisor}\}$
From our
assumption, we see that $S\neq \{\text{ }\}$.
By well-ordering principle, we can find a
least element $“a”$ in $S$.
Since $a
\in S$, then $“a”$ with no prime divisor.
Furthermore,
because $a|a$, then we conclude that $“a”$ is not a prime, then $“a”$ is a
composite
Then, $a=\alpha\beta$,
$1<\alpha <a$, $1<\beta < a$
Since $\alpha
< a$, and $“a”$ is the least element in $S$, then $\alpha \notin S$. Thus, $\alpha
\notin S$ implies $\alpha$ has a prime divisor $p$.
Hence,
we have $p|\alpha$.
$\therefore
p|\alpha$ and $a|\alpha \Rightarrow p|a$ which is impossible
$\therefore$
Thus, the assumption is false.
8) Proof that:
There
are infinitely many primes
Solution:
We prove
by contradiction. Assume the statement is wrong, then there are finitely many
primes.
Let $p_{1},p_{2},p_{3},…,p_{k}$
be all these primes.
Consider,
$$P=p_{1}p_{2}p_{3}…p_{k}
+1$$
Since $P>1$,
by the proof of “Every positive integer greater than $1$ has a prime divisor”,
$P$ has a prime divisor $q$, which means $q$ is a prime
$$\Rightarrow
q|P$$
If $q\neq
p_{i}$ for all $i=1,2,3,…,k$, then $q$ is a prime different from the one listed
above, which mean is impossible
On the
other hand, if $q=p_{i}$ for some $i=1,2,3,…,k$, then
$$q|p_{1}p_{2}p_{3}…p_{k}$$
Since $q|P$,
then we see that
$$q|(P -
p_{1}p_{2}p_{3}…p_{k})$$
Which implies
$q|1$
Because $q|1$
and $q$ is a prime, which is also impossible
Thus,
our assumption is wrong. There should be infinitely many prime.
9) Proof that:
If $n$
is a composite integer, then $n$ has a prime factor not exceeding $\sqrt{n}$
Solution:
Given
$n$ is composite, then $n=ab$, where $1<a<n$ and $1<b<n$
We can
deduce that $1< a \le b < n$, without lost of generality
Since
$a>1$, then $“a”$ has a prime divisor $q \Rightarrow q|a$
We next
argue that $a \le \sqrt{n}$:
Prove by
contradiction, we assume $a>\sqrt{n}$
Since $b
\ge a > \sqrt{n} \Rightarrow ab > \sqrt{n}\sqrt{n} \Rightarrow ab>n$ which
is impossible
$\therefore
a \le \sqrt{n}$
Since $n=ab
\Rightarrow a|n$ and $“a”$ has a prime divisor $q\Rightarrow q|a$, then $q|n$
Since $a\le
\sqrt{n}$ & $q|a \Rightarrow q\le a$, then $q\le \sqrt{n}$
10) Proof that:
Let $a,b
\in \mathbb{Z}, gcd(a,b) =d$, then $gcd(\frac{a}{d},\frac{b}{d})=1$
Solution:
Suppose
$gcd(\frac{a}{d},\frac{b}{d})=t$, then $t|\frac{a}{d}$ and $t|\frac{b}{d}$
Which mean
$\frac{a}{d}=tk_{1}$ and $\frac{b}{d}=tk_{2}$, $k_{1},k_{2} \in \mathbb{Z}$
Thus, we
have $a = tdk_{1}$ and $b=tdk_{2}$, which implies $td$ is common divisor for $a$
and $b$.
$$td \le
gcd(a,b) = d$$
$$\therefore
td\le d$$
$$\Rightarrow
t \le 1,t \in \mathbb{Z},t\neq 0$$
$$\Rightarrow
t=1$$
$\therefore
gcd(\frac{a}{d},\frac{b}{d})=1$
Comments
Post a Comment