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$