Explore BrainMass

Explore BrainMass

    Unique Factorization Prime/Co-Prime

    Not what you're looking for? Search our solutions OR ask your own Custom question.

    This content was COPIED from BrainMass.com - View the original, and get the already-completed solution here!

    1. Prove that a and b are coprime if and only if no prime numbers divides both a and b
    2. Show that [a,m] = m if and only if a divides m

    © BrainMass Inc. brainmass.com September 27, 2022, 4:48 pm ad1c9bdddf
    https://brainmass.com/math/number-theory/unique-factorization-prime-co-prime-527365

    SOLUTION This solution is FREE courtesy of BrainMass!

    For question 1. Recall, two numbers are called co-prime when their greatest common divisor gcd(a,b)=1 (Some might use (a,b), it's just a matter of notation). Now let's think about this: suppose there exists a prime that divides both a and b, then p is a common divisor of a,b. gcd(a,b) is the greatest common divisor, so certainly we have gcd(a,b)>=p. But as a prime, p is at least 2, so this implies gcd(a,b)>1. But this implies a, b are not co-prime.

    So, what do we get? We assumes there exists a prime that both divides a,b, and we get a contradiction that a,b are not co-prime. Hence if a,b are co-prime, then there cannot be a prime that divides both of them.

    For question 2. Recall [a,m] is the least common multiple.

    Suppose a can divide m, then m is a multiple of a. Notice m is also a multiple of itself. Hence m is a common multiple of a,m. But for any multiple of m, it must be at least m. This implies m itself is the least common multiple of a, m, which tells us m=[a,m]

    On the other hand, if [a,m]=m, then m is the least common multiple of a,m, meaning m is a multiple of a. This shows a can divide m.

    This content was COPIED from BrainMass.com - View the original, and get the already-completed solution here!

    © BrainMass Inc. brainmass.com September 27, 2022, 4:48 pm ad1c9bdddf>
    https://brainmass.com/math/number-theory/unique-factorization-prime-co-prime-527365

    ADVERTISEMENT