# Unique Factorization Prime/Co-Prime

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

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.

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