Results 1 to 2 of 2

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

  1. #1
    Newbie demdirbu's Avatar
    Joined
    Oct 2008
    From
    US
    Posts
    2

    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.

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

  2. #2
    Junior Member
    Joined
    Oct 2008
    Posts
    64
    Use definition!
    For example by definition 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 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.

    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: October 19th 2010, 10:50 AM
  2. Replies: 0
    Last Post: June 29th 2010, 08:48 AM
  3. [SOLVED] direct proof and proof by contradiction
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: February 27th 2010, 10:07 PM
  4. Proof with algebra, and proof by induction (problems)
    Posted in the Discrete Math Forum
    Replies: 8
    Last Post: June 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: April 14th 2008, 04:07 PM

Search Tags


/mathhelpforum @mathhelpforum