The greatest common divisor of more than two numbers

The gcd of three integers $a,b,c$ is denoted by $(a,b,c)$ and is defined by the relation $(a,b,c) =(a,(b,c)) = ((a,b),c)$.

The Euclidean algorithm

Given integers $a$ and $b$ with $b > 0$, there exists a unique pair of integers $q$ and $r$ such that $ a = bq+r$, with $0 \le r < b$. Moreover, $r=0$ if, and only if, $b|a$.

Proof. TODO

The Euclidean algorithm. Given positive integers a and b, where $b\not | a$. Let $r_0=a, r_1=b$, and apply the division algorithm repeatedly to obtain a set of remainders $r_2,r_3,...,r_n,r_{n+1}$ defined successively b the relations

                       $ r_0 = r_1q_1 + r_2,  \;\; 0<r_2<r_1,$
                       $ r_1 = r_2q_2 + r_3,  \;\; 0<r_3<r_2,$
                                              .
                                              .
                                              .
                       $ r_{n-2} = r_{n-1}q_{n-1} + r_n,  \;\; 0<r_n<r_{n-1},$
                       $ r_{n-1} = r_{n}q_{n} + r_{n+1},  \;\; r_{n+1}=0,$

Then $r_n$, the last nonzero remainder is the gcd of $a$ and $b$. 

Proof. TODO

The series of reciprocals of the primes

The infinite series $\sum_{n=1}^{\infty} \frac{1}{p_n}$ diverges.

Proof. suppose  $\sum_{n=1}^{\infty} \frac{1}{p_n}$ converges. So  $\sum_{n=k+1}^{\infty} \frac{1}{p_n} < \frac{1}{2}$. Let $Q=p_0p_1...p_k$, hence $1+nQ$ is not divisible by any $p_0,p_1,...,p_k$. So $1+nQ = p_{k+1}p_{k+2}...p_m$. By consequence $\frac{1}{1+nQ} \le \sum_{k+1}^{\infty}\frac{1}{p_i} < \frac{1}{2}$. Gives $\sum_n \frac{1}{1+nQ} \le \sum_n \left( \frac{1}{2}\right)^n$, which implies $\sum_n \frac{1}{1+nQ} $ to converge, which is false as can be shown by the integral test: Let $f(n) = \frac{1}{1+nQ}$, $f$ is positive and monotone decreasing, and $\int_1^{\infty} f(n) =  \lim_{n \rightarrow \infty} \left[ \frac{log(1+nQ)}{Q} \right]_1^{\infty} = \infty$.

The fundamental theorem of arithmetic

Every integer $n >1$ can be represented as a product of prime factors in only one way, apart from the order of the factors.

Proof.  By induction on $n$, it's verified for $n=2$. Suppose it is true for integers $<n$ and assume $n$ has two different prime factorizations $p_0p_1p_2...p_k = q_0q_1q_2...q_k=n$, then  $p_0|q_0q_1q_2...q_k$. So there is a $q_m \in \{q_0,q_1,...,q_k\}$ such that $p_0=q_m$ set it to

$q_0$. Hence $1<n/p_0=p_1p_2...p_k<n$. By induction hypothesis $p_1p_2...p_k$ is a unique

factorization, then so is $p_0p_1p_2...p_k=n$.

Let $a=\prod_{i=1}^{\infty}p_i^{a_i}$, $b=\prod_{i=1}^{\infty}p_i^{b_i}$, then $(a,b)=\prod_{i=1}^{\infty}p_i^{c_i}$ where $c_i=min{a_i,b_i}$.

Proof. Let $d=(a,b)$, then there exists $x,y\in\mathbb{N}$ such that $d = ax+by$. Let $k|a$ and $k|b$, hence $k|(ax+by=d)$. So $d$ is the greatest divisor of both $a$ and $b$.

Some prime numbers properties

Every integer $n>1$ is either a prime number or a product of primes.

Proof. Sieve of Eratosthenes algorithm gives an impression of this result. However here is a simple proof by Euclid: By induction on n, for $n=2$ this is true. Let's suppose it's true for every integer $<n$. If $n$ is not prime then, there exists an integer $d \ne n$ such that $d|n$, hence $n=kd$ where $k,d < n$ and $k,d>1$. By induction hypothesis $k,d$ are products of primes, so is $n$.

There are infinitely many prime numbers.

Proof. Euclid. let $N=1+\prod_{i=0}^{n}p_i$. Hence $N > 1$, so it's either prime or a product of primes. $N$ is neither prime nor a product of primes which contradicts previous result.

If a prime doesn't not divide a, then $(p,a)=1$.

Proof. Let $(p,a) =d$, then $d \ne p$ and $d | p$, hence $d=1$.

If a prime p divides ab, then $p|a$ or $p|b$. 

Proof. Suppose $p \not | a$, hence $(p,a)=1$, then according to Euclid's lemma, $p|b$.

Introduction to Analytic Number Theory - Tom M. Apostol

I have received this amazing book last week and can't wait to go through it all. Going through the first chapter I already get the impression it's well detailed and well organised. I will be posting notes and important formulas throughout the adventure.