Prove that if gcd(a,b)=1 and if c divides b, then gcd(a,c)=1.

Printable View

- April 9th 2008, 09:25 PMLeileinumber theory
Prove that if gcd(a,b)=1 and if c divides b, then gcd(a,c)=1.

- April 9th 2008, 09:39 PMshawn
Suppose gcd(a,b) = 1.

That is, b=1k and a = 1m for some integers k,m.

Suppose b|c that is, c = bx for some integers x.

Then c = (1k)x where 1k is an integer.

I think now you need to show that k = 1 because a = 1m (and so 1 is the largest divisor of a).

That's all I've got...it might not be complete or correct. Can someone double check it? - April 9th 2008, 10:13 PMangel.white
Might be too wordy, I'm not really good at these, but I think it includes everything it needs to:

***if**gcd(a,b)=1**then**a and b have no common elements in their prime factorizations

***if**c|b**then**c must be entirely composed of elements from b's prime factorization

***therefore**there are no common elements in a and c's prime factorization

***therefore**the greatest common denominator of a and c is 1.

==================================================

**Attempt at a formal proof:**

Let A be the set of prime integers which occur in a's prime factorization.

Let B be the set of prime integers which occur in b's prime factorization.

Let and where k and j are integers used to denote which element is being taken from the set.

Let n be the cardinality of A (n = # of elements in a's prime factorization)

Let m be the cardinality of B (m = # of lements in b's prime factorization)

Then

and

If there were any elements such that then said element would divide both A and B, because it is common to both of their prime factorizations. As such, the sets A and B would intersect at that element.

Therefore the

So the sets A and B cannot intersect.

---------

Let c be an integer, and C be the set of prime integers which occur in c's prime factorization.

If c|b then C must be a subset of B (**every**element in C is an element in B)

Because C is a subset of B, and B does not intersect A, C must not intersect A (there can be no common elements in c's prime factorization and a's prime factorization).

Therefore the gcd(a,c) = 1 - April 10th 2008, 12:01 AMCaptainBlack
- April 10th 2008, 08:04 AMThePerfectHacker