# gcd(a,b)=pi^min{si,ti} and lcm(a,b)=pi^max{si,ti} proof?

• Oct 8th 2008, 11:43 PM
demdirbu
gcd(a,b)=pi^min{si,ti} and lcm(a,b)=pi^max{si,ti} proof?
a>1 , b>1 are two integers(whole numbers)

s>=0 , t>=0

a=(P1^s1)*...*(Pr^sr)

b=(P1^t1)*...*(Pr^tr)

for each i=1,2,3,....,r is mi=min{si,ti} and ni=max{si,ti}.

show that : gcd(a,b)=(P1^m1)*...*(Pr^mr)

lcm(a,b)=(P1^n1)*...*(Pr^nr)

I've tried to ask the question as the way it is

Hope I'm clear enogh.

I would be glad if you explain the answers step by step.

For example by definition $g=gcd(a,b)$
since $m_i\leq s_i and m_i\leq t_i$ then $p_i^{m_i}$divides both $p_i^{s_i}$ and $p_i^{t_i}$. Hence $p_1^{m_1}\cdots p_k^{m_k}$ divides both a and b.
Now supposed d divides $a=p_1^{s_1}\cdots p_k^{s_k}$ and let q be any of prime factor of d. Since d divides a then q must be one of $\{p_1,\cdots, p_k\}$. Then the prime factors of d are also $\{p_1,\cdots, p_k\}$. So we can write $d=p_1^{u_1}\cdots p_k^{u_k}$ where $u_i\leq s_i$. By doing the same thing with respect to b, we also have $u_i\leq t_i$. Hence $u_i\leq min\{s_i,t_i\}$. Then it follows that g divides d.