State and Prove Fundamental Theorem of Arithmetic. Prove that every positive integer $n > 1$ is either a prime or can be written as a product of primes; this representation is unique, apart from the order in which the factors occur.

  (Fundamental Theorem of Arithmetic): Every positive integer $n > 1$ is either a prime or can be written as a product of primes; this representation is unique, apart from the order in which the factors occur.

Proof: If a positive integer $n > 1$ is a prime number, then we are done. So suppose that $n$ is a composite number. Therefore there exists an integer $d$ satisfying $d ~|~ n$ and $1 < d < n$. By Well-Ordering Principle, there exists smallest integer among all such integers $d$ (positive divisors), we will called this smallest integer (smallest positive divisor) as a $p_{1}$. We claim that $p_{1}$ is a prime number. Suppose that $p_{1}$ is not a prime number. So there exists  an integer $q$ satisfying $q ~|~ p_{1}$ and $1 < q < p_{1}$. Since $q ~|~ p_{1}$ and $p_{1} ~|~ n$, we will get $q ~|~ n$, a contradiction to choice of smallest positive divisor  $p_{1}$ of $n$.

Therefore we can write $n$ as $n = p_{1} \cdot n_{1}$, where $p_{1}$ is a prime number and $1 < n_{1} < n$. If $n_{1}$ is a prime number, then we are done. Suppose $n_{1}$ is not a prime number, then the argument is repeated to produce a second prime number $p_2$ such that $n_{1} = p_2 \cdot n_2$ where $p_2$ is a prime number and $1 < n_2 < n_{1}$. So we can write $n$ as $n = p_{1} \cdot p_2 \cdot n_2$. If $n_2$ is a prime number, then we are done. Suppose $n_2$ is not a prime number, we produce a third prime number $p_3$ such that $n_2 = p_3 \cdot n_3$ where $p_3$ is a prime number and $1 < n_3 < n_2$. So we can write $n$ as $n = p_{1} \cdot p_2 \cdot p_3 \cdot n_3$. we continue this process, we will get decreasing sequence $n > n_{1} > n_2 > n_3 > \cdots > 1 $. This decreasing sequence cannot continue indefinitely, so that after a finite number of steps $n_{k-1}$ is a prime, call it, $p_{k}$· This gives prime factorization of $n$ as $n = p_{1} \cdot p_2 \cdot p_3 ~\cdots~ p_k$.

Now, we prove the uniqueness of the prime 

factorization. Suppose that the integer $n$ can be represented as a product of primes in two ways; say, $n = p_{1} \cdot p_2 \cdot p_3 ~\cdots~ p_r = q_{1} \cdot q_2 \cdot q_3 ~\cdots~ q_s$ with $r < s$ where $p_i$ and $q_j$ are prime numbers. written in increasing magnitude so that 

$p_{1} < p_2 <  p_3 < \cdots < p_r$ and  $q_{1} < q_2 <  q_3 < \cdots < q_s$

Since $p_{1} ~|~ q_{1} \cdot q_2 \cdot q_3 ~\cdots~ q_s$, by Corollary,  $ p_{1} = q_k $ for some $k$; 

but then $p_{1} \geq q_{1}$. similarly we can show that $q_{1} \geq p_{1}$. Hence $ p_{1} = q_{1}$. We will cancel 

this common factor and obtain 

$p_2 \cdot p_3 ~\cdots~ p_r = q_2 \cdot q_3 ~\cdots~ q_s$

Now repeat the process to get $ p_2 = q_2$. and obtain 

$p_3 \cdot p_4 ~\cdots~ p_r = q_3 \cdot q_4 ~\cdots~ q_s$ 

Continue in this fashion. If the inequality $r < s$ were to hold, we would eventually 

arrive at 

$1 = q_{r+l} \cdot q_{r+2} ~\cdots~ q_s$ 

which is absurd, because each $q_j > 1$. Hence, $r = s$ and $ p_{1} = q_{1},~ p_2 = q_2, ~\cdots~,  p_r = q_r$. Hence uniqueness of  prime factorization holds.


Corollary:  Any positive integer $n > 1 $ can be written uniquely (as a product of powers of primes) in a canonical form $n = p^{k_{1}}_{1} \cdot p^{k_2}_2 ~\cdots~ p^{k_r}_r $ 

where, for $i = 1, 2, ... , r$, each $k_i$ is a positive integer and each $p_i$ is a prime, with 

$p_{1} < p_2 < \cdots < p_r$.

Proof:  By above Theorem, we can write any positive integer $n > 1$ as a product of primes. Suppose that $n = p_{1} \cdot p_{1} \cdot p_{1} ~\cdots~ p_2 \cdot p_2 \cdot p_2  ~\cdots~ p_r \cdot  p_r \cdot  p_r ~\cdots~$, where $p_i$ is $k_i$ times. By collecting like primes and replacing them by a single factor we get the a canonical form $n = p^{k_{1}}_{1} \cdot p^{k_2}_2 ~\cdots~ p^{k_r}_r $ 

where, for $i = 1, 2, ... , r$, each $k_i$ is a positive integer and each $p_i$ is a prime, with $p_{1} < p_2 < \cdots < p_r$.

Popular posts from this blog

Definition of divisibility and Theorem on divisibility

  Definition: An integer $b$ is said to be divisible by an integer $a \not = 0$, if there exists some integer $c$ such that $ b = a \cdot c$. An integer $b$ is  divisible by an integer $a \not = 0$, is denoted by $a ~|~ b$.  We write $a \nmid b$ to indicate that $b$  is not divisible by $a$. Theorem: For integers $a, ~b, ~c$ the following hold: $1.$ $a ~|~ 0, ~ 1 ~|~ a, ~ a ~|~ a $. $2.$  $ a ~|~ 1 $ if and only if $a =  1$ or $a = -1$. $3.$  If $a ~|~ b$ and $c ~|~ d$, then $a \cdot c ~|~ b \cdot d$. $4.$   If $a ~|~ b$ and $b ~|~ c$, then $a ~|~ c$. $5.$  If $a ~|~ b$ and $b ~|~ a$ if and only if $a =  b$ or $a = -b$. $6.$  If $a ~|~ b$ and $b \not = 0$, then $|a| \leq |b|$. $7.$  If $a ~|~ b$ and $a ~|~ c$, then $a~ |~ (b \cdot x + c \cdot y)$ for arbitrary integers $x$ and $y$. Proof: $1.$ For any integer $a$, we can write $0 = a \cdot 0$, $a = 1 \cdot a$ and $a = a \cdot 1$. Theref...
Read more

The Division Algorithm / Prove that given integers $a$ and $b$, with $b > ~ 0$, there exist unique integers $q$ and $r$ such that $a = b \cdot q +r$, where $0 \leq r < b$. The integer $q$ is called the $\textbf{quotient}$ and the integer $r$ is called $\textbf{remainder}$.

Image
State and prove Division Algorithm theorem.  Theorem:  Given integers $a$ and $b$, with $b > ~ 0$, there exist unique integers $q$ and $r$ such that $a = b \cdot q +r$, where $0 \leq r < b$. The integer $q$ is called the $\textbf{quotient}$ and the integer $r$ is called $\textbf{remainder}$. Proof : Firstly, we will show that the set $S = \{a - x \cdot b \;|\; x \in \mathbb{Z}$ and $  a -x \cdot b \geq 0\}$ is nonempty.  For this purpose, we have to find value of $x$ such that $a -x \cdot b \geq 0$. Given that integer $b > 0$, i.e. $b \geq 1$. Multiply $b \geq 1$ by $|a|$, we get $|a|\cdot b \geq |a|$ and so $a - ( - |a|) \cdot b = a + |a| \cdot b \geq a + |a| \geq 0$. If we take $x = |a|$, then, $a -x \cdot b \in S$. This show that $S$ is nonempty subset of nonnegative integers. By the Well-Ordering Principle (for more details see  Well-Ordering Principle  ) , set $S$ contains a least integer; say it $r$. Since $r \in S$, there exists an i...
Read more

Define Greatest Common Divisor and Prove that if $a$ and $b$ are any integers, not both of them are zero. Then there exist integers $x$ and $y$ such that $gcd(a, b) =a \cdot x + b \cdot y$.

Image
Definition: Let $a$ and $b$ be any integers, with at least one of them is not zero. The greatest common divisor of $a$ and $b$, denoted by $gcd(a, b)$, is the positive integer $d$ satisfying the following: $1.$  $d ~|~ a$ and $d ~|~ b$. $2.$ If $c ~|~ a$ and $c ~|~ b$, then $c \leq d$. Theorem:  If $a$ and $b$ are any integers, not both of them are zero. Then there exist integers $x$ and $y$ such that $gcd(a, b) =a \cdot x + b \cdot y$. Proof:   Let  $a$ and $b$ be any integers, not both of them are zero. Consider the set $S = \{a \cdot u + b \cdot  v \;|\; a \cdot  u + b \cdot  v > 0$ and $ u, v \in \mathbb{Z}\}$, that is  $S$ is the set of all positive linear combinations of $a$ and $b$. Firstly, we will show  that $S$ is nonempty set. We have taken integers $a$ and $b$ such that not both of them are zero. Without loss of generality, suppose that $a \not = 0$. Then the integer $|a| = a \cdot u + b \cdot 0 \in S$ for the v...
Read more