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$.
No comments:
Post a Comment