Factorization of Primes and Greatest Common Divisors

Question

If $a=q_1^{e_1}q_2^{e_2}...q_r^{e_r}$ and $b=s_1^{f_1}s_2^{f_2},...s_u^{f_u}$ are the factorizations of $a$ and $b$ into primes, then there exist primes $t_1<t_2<...<t_v$ and nonnegative integers $g_i$ and $h_i$ such that $a=t_1^{g_1}t_2^{g_2}...t_v^{g_v}$ and $b=t_1^{h_1}t_2^{h_2}...t_u^{h_u}$.

Now, prove that g.c.d($a$,$b$)=$t_a^{c_1}t_2^{c_2}...t_v^{c_v}$ where each $c_i$ is the smaller of the corresponding $g_i$ and $h_i$

I really need help knowing where to even start.

Answer 1

HINT: $d = gcd(a,b) \Rightarrow d|a, d|b$ which gives every prime integer divides $d$ also divides both $a$ and $b$. So if $c_i$-th power of a a prime $t_i$ divides $d$ then $c_i$-th power of a a prime $t_i$ divides both $a$ and $b$. Again any prime integer divides both $a$ and $b$ will divides $d$. Hence if $c_i$-th power of a a prime $t_i$ divides both $a$ and $b$ will divides $d$. when we consider greatest common divisor we shall find out the prime integer whose greatest power divides both $a$ and $b$. So the minimum power of $t$ will divide both $a$ and $b$ as well as $d$. Now consider all prime divisors of $d$ to apply the Fundamental theorem of arithmetic.

Answer 2

The first part is easy. Just rename $q_1, \cdots ,q_r,s_1, \cdots, s_u$ into $t_1, \cdots, t_v$. It's obvious that $v \leq r+u$ because there are at most $r+u$ prime numbers in that list, unless some prime numbers in $q_1, \cdots, q_r$ and $s_1 \cdots s_u$ are common so we don't need to count them twice.

Now after you've renamed them you can write $a=t_1^{g_1} \cdots t_v^{g_v}$ where $g_i=e_i$ if $t_i=q_i$ and otherwise $g_i=0$. Notice that $0$ is accepted as an exponent because it's still a non-negative integer. You can do the same with $b$. Remember that you can always assume that the number of primes are the same in both factorizations for $a$ and $b$ because if a prime isn't present in the other one's factorization you can assume that its exponent is zero.

Now to prove the statement about $\gcd(a,b)$ you need to use the definition of $\gcd(a,b)$. Let's set $d=\gcd(a,b)$. Then by definition:

1. d>0
2. $d \mid a$ and $d \mid b$
3. if $e \mid a$ and $e \mid b$ then $e \mid d$

Particularly, the third property is important for us.

Note that if $x$ has the prime factorization $x=t_1^{g_1} \cdots t_v^{g_v}$ and y has the prime factorization $y=t_1^{h_1} \cdots t_v^{h_v}$ then $x \mid y$ if and only if $g_i \leq h_i$ for all $i=1,..v$

Now, suppose you've been given two numbers $x=t_1^{g_1}\cdots t_v^{g_v}$ and $y=t_1^{h_1}\cdots t_v^{h_v}$ and set $d=|t_1^{c_1} \cdots t_v^{c_v}|$ where $c_i=\min\{g_i,h_i\}$ . We claim that $d=\gcd(x,y)$:

It's obvious that $d>0$. Also, it's clear that $d \mid a$ and $d \mid b$ because $c_i \leq g_i$ and $c_i \leq h_i$. Now if there is any other number $e=t_1^{k_1} \cdots t_v^{k_v}$ such that $e \mid a$ and $e \mid b$ then $t_i \leq a$ and $t_i \leq b$. But that means $t_i \leq \min\{a,b\}=c_i$. That proves $e \mid d$.