1. Greatest Common Divisor
Elementary Number Theory is study of the integers $\mathbb{Z}$ without using techniques from other fields such as real and complex analysis, algebra, and topology. The subject does not assume any prerequisites other than mathematical fundamentals such as elementary set theory. The notes are based on the course that I am currently taking in UCLA from professor Chandrashekhar Khare.
This series will heavily follow: Underwood Dudley, Elementary Number Theory. (Amazon)
Definition: $a,b \in \mathbb{Z}$, then we say that $a$ divides $b$, or $b$ is divided by $a$ if there exists $c \in \mathbb{Z}$ such that $ac = b$ and denote it $a|b$.
Example:
1) $12|60$ because $5 \cdot 12 = 60$
2) $3 \not \mid 10$
3) $a|0$ for all $a \in \mathbb{Z}$ as $0 = 0 \cdot a$.
Lemma: If $d|a$ and $d|b$, then $d|a+b$.
Proof) There exist $c_1, c_2$ such that $c_1d = a, c_2d = b$. Adding the two equations we get $d(c_1+c_2) | a+b$. As $c_1+c_2 \in \mathbb{Z}$. By definition $d|a+b$.
The we can generalize the lemma as follows:
Lemma: (generalized) If $d|a_i$ and $c_i \in \mathbb{Z}$ for $i=0, \ldots, r$, then $d| \sum_{i=1}^r c_ia_i$.
Proof) There exists $m_i \in \mathbb{Z}$ such that $dm_i = a_i$. Multiply $c_i$ on both side, then we get $dc_im_i = c_ia_i$. Add them all together to get
\[ d(\sum_{i=1}^r c_i m_i) = \sum_{i=1}^r c_i a_i \]
Again by definition, $d| \sum_{i=1}^r c_ia_i$.
In order to define the greatest common divisor, we need a statement that is equivalent of choice of axiom. For those who do not know the choice of axiom or the well-ordering axiom, just consider it as a self-evident statement that cannot be proved, and has to be assumed. Well-ordering Axiom takes two forms: "Least Integer Principle" says that
Any nonempty set $S$ of integers that is bounded below has a smallest element. (i.e. there exists $m \in S$ such that $s \geq m$ for all $s \in S$)
And equivalently, "Greatest integer Principle" says that
Any nonempty set $S$ of integers that is bounded above has a largest element. (i.e. there exists $m \in S$ such that $s \leq m$ for all $s \in S$.)
Definition: Let $a,b \in \mathbb{Z}$ not both equal to $0$, then we say that an integer $d$ is the greatest common divisor(gcd) denoted $gcd(a,b)$ of $a,b$ if $d=gcd(a,b)$ satisfies the following properties:
1) $d|a$ and $d|b$
2) If $c$ is such that $c|a$ and $c|b$, then $c \leq d$.
Equivalently,
2') If $c$ is such that $c|a$ and $c|b$, then $c |d$.
It is easy to see that $2') \Rightarrow 2)$, but the converse will need justification.
Remark: 1) $gcd(0,0)$ is not well-defined as any number can divide $0$, hence there is no "greatest" such divisor.
2) The set $\{$ common divisors of $a$ and $b \}$ is bounded above by the $max \{ \pm a, \pm b \}$, and it is nonempty because $1|a$ and $1|b$, hence we can define $gcd(a,b)$ to be the largest element, hence we have shown that there exists the greatest common divisor.
3) Suppose we have two $d,d'$ greatest common divisor, then $d \leq d'$ and $d' \leq d$ by 2) property of the greatest divisors above, hence $d=d'$.
4) As $1$ is a divisor of all integer $gcd(a,b) \geq 1$.
Examples: $gcd(6,45) = 3$, $gcd(8,-32)$, $gcd(-3,0) = 3$ and $gcd(17, 19) =1$.
Definition: Let $a,b \in \mathbb{Z}$, and $gcd(a,b)=1$ (i.e. they don't share any common divisor other than $\pm 1$), then $a$ and $b$ is relatively prime (or coprime).
This series will heavily follow: Underwood Dudley, Elementary Number Theory. (Amazon)
Definition: $a,b \in \mathbb{Z}$, then we say that $a$ divides $b$, or $b$ is divided by $a$ if there exists $c \in \mathbb{Z}$ such that $ac = b$ and denote it $a|b$.
Example:
1) $12|60$ because $5 \cdot 12 = 60$
2) $3 \not \mid 10$
3) $a|0$ for all $a \in \mathbb{Z}$ as $0 = 0 \cdot a$.
Lemma: If $d|a$ and $d|b$, then $d|a+b$.
Proof) There exist $c_1, c_2$ such that $c_1d = a, c_2d = b$. Adding the two equations we get $d(c_1+c_2) | a+b$. As $c_1+c_2 \in \mathbb{Z}$. By definition $d|a+b$.
The we can generalize the lemma as follows:
Lemma: (generalized) If $d|a_i$ and $c_i \in \mathbb{Z}$ for $i=0, \ldots, r$, then $d| \sum_{i=1}^r c_ia_i$.
Proof) There exists $m_i \in \mathbb{Z}$ such that $dm_i = a_i$. Multiply $c_i$ on both side, then we get $dc_im_i = c_ia_i$. Add them all together to get
\[ d(\sum_{i=1}^r c_i m_i) = \sum_{i=1}^r c_i a_i \]
Again by definition, $d| \sum_{i=1}^r c_ia_i$.
In order to define the greatest common divisor, we need a statement that is equivalent of choice of axiom. For those who do not know the choice of axiom or the well-ordering axiom, just consider it as a self-evident statement that cannot be proved, and has to be assumed. Well-ordering Axiom takes two forms: "Least Integer Principle" says that
Any nonempty set $S$ of integers that is bounded below has a smallest element. (i.e. there exists $m \in S$ such that $s \geq m$ for all $s \in S$)
And equivalently, "Greatest integer Principle" says that
Any nonempty set $S$ of integers that is bounded above has a largest element. (i.e. there exists $m \in S$ such that $s \leq m$ for all $s \in S$.)
Definition: Let $a,b \in \mathbb{Z}$ not both equal to $0$, then we say that an integer $d$ is the greatest common divisor(gcd) denoted $gcd(a,b)$ of $a,b$ if $d=gcd(a,b)$ satisfies the following properties:
1) $d|a$ and $d|b$
2) If $c$ is such that $c|a$ and $c|b$, then $c \leq d$.
Equivalently,
2') If $c$ is such that $c|a$ and $c|b$, then $c |d$.
It is easy to see that $2') \Rightarrow 2)$, but the converse will need justification.
Remark: 1) $gcd(0,0)$ is not well-defined as any number can divide $0$, hence there is no "greatest" such divisor.
2) The set $\{$ common divisors of $a$ and $b \}$ is bounded above by the $max \{ \pm a, \pm b \}$, and it is nonempty because $1|a$ and $1|b$, hence we can define $gcd(a,b)$ to be the largest element, hence we have shown that there exists the greatest common divisor.
3) Suppose we have two $d,d'$ greatest common divisor, then $d \leq d'$ and $d' \leq d$ by 2) property of the greatest divisors above, hence $d=d'$.
4) As $1$ is a divisor of all integer $gcd(a,b) \geq 1$.
Examples: $gcd(6,45) = 3$, $gcd(8,-32)$, $gcd(-3,0) = 3$ and $gcd(17, 19) =1$.
Definition: Let $a,b \in \mathbb{Z}$, and $gcd(a,b)=1$ (i.e. they don't share any common divisor other than $\pm 1$), then $a$ and $b$ is relatively prime (or coprime).
Comments
Post a Comment