number theory

• Apr 9th 2008, 09:25 PM
Leilei
number theory
Prove that if gcd(a,b)=1 and if c divides b, then gcd(a,c)=1.
• Apr 9th 2008, 09:39 PM
shawn
Quote:

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?
• Apr 9th 2008, 10:13 PM
angel.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 $\displaystyle A_k \in A$ and $\displaystyle 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 $\displaystyle a = A_1*A_2*A_3*...*A_n$
and $\displaystyle b = B_1*B_2*B_3*...*B_m$

If there were any elements such that $\displaystyle 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 $\displaystyle 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
• Apr 10th 2008, 12:01 AM
CaptainBlack
Quote:

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: $\displaystyle b=1 \times b$ and $\displaystyle a=1 \times a$, we have $\displaystyle k=b$ and $\displaystyle m=a$.

RonL
• Apr 10th 2008, 08:04 AM
ThePerfectHacker
Quote:

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

Let $\displaystyle d=\gcd(a,c)$, thus, $\displaystyle d|a$ and $\displaystyle d|c$. But $\displaystyle c|b$ thus $\displaystyle d|b$. This forces $\displaystyle d=1$ because $\displaystyle \gcd(a,b)=1$.