Fundamental Theorem of Arithmetic

 

정리1

$p$ is a prime,  $p|ab$

$\Rightarrow$  $p|a$  or  $p|b$

 

  Case 1 : $p|a$

  we are done

 

  Case 2 : $p \!\!\! \not | a$

  Then, $gcd(a,p)=1$

  So there exist $x,y \in \mathbb{Z}$  s.t.  $ax+py=1$

  $\Rightarrow$ $abx+pby = b$

  since $p|ab$  and  $p|p$,

  so $p|abx+pby$

  $\therefore$   $p|b$

 

 

 

따름정리 Prime Divisibility Property (PDP)

$p$ is a prime,  $p|a_{1}a_{2} \cdots a_{n}$

$\Rightarrow$  $p|a_{i}$  for some $i$

 

 

 

정리2 Fundamental Theorem of Arithmetic (FTA)

Let $n$ be an integer and $n \geq 2$

1. $n$ can be factored into a product of primes.

(i.e. there exist primes $p_{1}, p_{2}, \cdots, p_{r}$   s.t.   $n=p_{1}p_{2} \cdots p_{r}$)

 

2. $n$ is factored into a product of primes in a "unique" way :

           Suppose $n = p_{1}p_{2} \cdots p_{r}$ and $n = q_{1}q_{2} \cdots q_{s}$ where $p_{i}, \; q_{i}$ are primes.

           Then $r=s$ and $[p_{1}, p_{2}, \cdots, p_{r}] = [q_{1}, q_{2}, \cdots, q_{s}] $ as multisets.

(i.e. $r=s$, and after rearranging $q_{i}'s$ if necessary, $p_{i} = q_{i}$ for all $i$.)

 

pf)

  We use mathematical induction on $n$ when $n=2$, it holds since $2$ is a prime.

  Suppose FTA - 1 holds for $n \leq k$ for some $k \geq 2$

  Let $n=k+1$

 

  Case 1 : $k+1$ is a prime

  Done

 

  Case 2 : $k+1$ is not a prime

  Then $k+1 = ab$ for some integers $2 \leq a,b \leq k$.

  By the induction hypothesis,

  $a=p_{1}p_{2} \cdots p_{r}$  and  $b=q_{1}q_{2} \cdots q_{s}$ for some primes $p_{i}, \; q_{i}$

  $\therefore$  $n = k+1 = ab = p_{1}p_{2} \cdots p_{r} q_{1}q_{2} \cdots q_{s}$ is a product of primes.

 

  WLOG WMA $r \leq s$

  (without loss of generality, we may assume)

  Then, $p_{1} |  n = q_{1}q_{2} \cdots q_{s}$

  By PDP, we get $p_{1} | q_{i}$ for some $i$. Since $q_{i}$ is also a prime, so $p_{1} = q_{i}$.

  Rearrange $q_{j}'s$ so that $p_{1} = q_{1}$.

  So $ p_{1}p_{2} \cdots p_{r} = p_{1}q_{2} \cdots q_{s}$

  $\Rightarrow$ $ p_{2} \cdots p_{r} = q_{2} \cdots q_{s}$

  Repeat this process for finitely many times

 

  Suppose 1 : $r<s$

  Then we get $1 = q_{r+1}q_{r+2} \cdots q_{s}$

  Since $q_{i}'s$ are primes,

  Contradiction

 

  $\therefore$  $r=s$

  During the above process, we also showed that $p_{i} = q_{i}$ $(1 \leq i \leq r)$ after rearranging $q_{i}'s$.