Results 1 to 2 of 2

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

  1. #1
    Newbie demdirbu's Avatar
    Oct 2008

    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



    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)


    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.

    Thanks in advance.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Junior Member
    Oct 2008
    Use definition!
    For example by definition $\displaystyle g=gcd(a,b)$
    1) if g is a factor of a and b and i
    2) if d is another factor of a and b then g divides d.

    since $\displaystyle m_i\leq s_i and m_i\leq t_i$ then $\displaystyle p_i^{m_i} $divides both $\displaystyle p_i^{s_i}$ and $\displaystyle p_i^{t_i}$. Hence $\displaystyle p_1^{m_1}\cdots p_k^{m_k}$ divides both a and b.

    Now supposed d divides $\displaystyle 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 $\displaystyle \{p_1,\cdots, p_k\}$. Then the prime factors of d are also $\displaystyle \{p_1,\cdots, p_k\}$. So we can write $\displaystyle d=p_1^{u_1}\cdots p_k^{u_k}$ where $\displaystyle u_i\leq s_i$. By doing the same thing with respect to b, we also have $\displaystyle u_i\leq t_i$. Hence $\displaystyle u_i\leq min\{s_i,t_i\}$. Then it follows that g divides d.

    The same (similar) argument also works for lcm.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 5
    Last Post: Oct 19th 2010, 10:50 AM
  2. Replies: 0
    Last Post: Jun 29th 2010, 08:48 AM
  3. [SOLVED] direct proof and proof by contradiction
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: Feb 27th 2010, 10:07 PM
  4. Proof with algebra, and proof by induction (problems)
    Posted in the Discrete Math Forum
    Replies: 8
    Last Post: Jun 8th 2008, 01:20 PM
  5. proof that the proof that .999_ = 1 is not a proof (version)
    Posted in the Advanced Applied Math Forum
    Replies: 4
    Last Post: Apr 14th 2008, 04:07 PM

Search Tags

/mathhelpforum @mathhelpforum