Results 1 to 5 of 5

Math Help - number theory

  1. #1
    Newbie
    Joined
    Feb 2008
    Posts
    7

    number theory

    Prove that if gcd(a,b)=1 and if c divides b, then gcd(a,c)=1.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Junior Member
    Joined
    Feb 2008
    Posts
    51
    Quote Originally Posted by Leilei View Post
    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?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member angel.white's Avatar
    Joined
    Oct 2007
    Posts
    723
    Awards
    1
    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
    Last edited by angel.white; April 10th 2008 at 12:20 AM.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by shawn View Post
    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
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    Quote Originally Posted by Leilei View Post
    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.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Textbooks on Galois Theory and Algebraic Number Theory
    Posted in the Advanced Algebra Forum
    Replies: 3
    Last Post: July 8th 2011, 06:09 PM
  2. Number Theory
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: May 19th 2010, 07:51 PM
  3. Number Theory
    Posted in the Advanced Algebra Forum
    Replies: 4
    Last Post: February 16th 2010, 05:05 PM
  4. Replies: 2
    Last Post: December 18th 2008, 05:28 PM
  5. Number theory, prime number
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: September 17th 2006, 08:11 PM

Search Tags


/mathhelpforum @mathhelpforum