# Math Help - number theory

1. ## number theory

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

2. Originally Posted by Leilei
Prove that if gcd(a,b)=1 and if c divides b, then gcd(a,c)=1.
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?

3. 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 $A_k \in A$ and $B_j \in B$ 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 $a = A_1*A_2*A_3*...*A_n$
and $b = B_1*B_2*B_3*...*B_m$

If there were any elements such that $B_j = A_k$ 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 $gcd(a,b) = B_j = A_k \not{=} 1$

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

4. Originally Posted by shawn
Suppose gcd(a,b) = 1.
That is, b=1k and a = 1m for some integers k,m.
This is trivialy true and in no way uses the fact that gcd(a,b)=1.

In fact as: $b=1 \times b$ and $a=1 \times a$, we have $k=b$ and $m=a$.

RonL

5. Originally Posted by Leilei
Prove that if gcd(a,b)=1 and if c divides b, then gcd(a,c)=1.
Let $d=\gcd(a,c)$, thus, $d|a$ and $d|c$. But $c|b$ thus $d|b$. This forces $d=1$ because $\gcd(a,b)=1$.