GCD with prime factorisation demonstration

Question

Let $$a=p_{1}^{\alpha_{1}}...p_{r}^{\alpha_{r}}$$ be prime factorisation of a.

Let $$b=p_{1}^{\beta_{1}}...p_{r}^{\beta_{r}}$$ be prime factorisation of b.

Let $$\gamma_{i}= Min(\alpha_{i},\beta_{i}), i=1,...,r$$

Show that $$GCD(a,b)=p_{1}^{\gamma_{1}}...p_{r}^{\gamma_{r}}$$

Any suggestions?

Answer 1

Let $GCD(a,b)=d=p_{1}^{\lambda_{1}}......p_{r}^{\lambda_{r}}. $ Let ${\lambda_{i}\geq\gamma_{i}}.$ Then $p_{i}^{\alpha_{i}}\leq p_{i}^{\lambda_{i}}.$ Hence $p_{i}^{\lambda_{i}} $will not devide $p_{i}^{\alpha_{i}}$. hence D will not devide a. Thus d is not GCD. Hence $\lambda_{i}=\gamma_{i}$

Answer 2

1. Show that it is a divisor of both $a$ and $b$
2. Show that no larger number is a divisor of both at the same time

For this you need to know how to tell from the prime factorisation whether one number divides another. Do you know how to do that?

Answer 3

let$\gamma_i\gt\min(a_i,b_i)$ then it GCD won't divide $a_i or b_i$

which is a contradiction to definition of GCD