Results 1 to 6 of 6

Math Help - pairwise prime

  1. #1
    Junior Member
    Joined
    Sep 2008
    Posts
    62

    pairwise prime

    Let a,a2,...,an c with a1, a2,...,an pairwise relatively prime. Prove that if ai c for each i, then a1,a2,...an c

    so far:
    gcd(a1,a2,an)=1 since its pairwise then gcd (a1,an) =1, gcd (a2,an)=1
    gcd(ai,aj)=1

    c=ai*m
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2008
    From
    Paris, France
    Posts
    1,174
    I'd suggest you to procede by induction.

    Show that if a_1\cdots a_k|c, then a_1\cdots a_ka_{k+1}|c. Hint: remark that a_1\cdots a_k and a_{k+1} are relatively prime (this by the way could be proved by induction).
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Sep 2008
    Posts
    62
    Quote Originally Posted by Laurent View Post
    I'd suggest you to procede by induction.

    Show that if a_1\cdots a_k|c, then a_1\cdots a_ka_{k+1}|c. Hint: remark that a_1\cdots a_k and a_{k+1} are relatively prime (this by the way could be proved by induction).

    Hey no clue if i did this right but does it go something like this??

    f(k)=a1....ak
    f(k+1)=a1....ak,ak+1
    f(k+1)-f(k)=a1....ak,ak+1-a1....ak
    =a1....ak(ak+1-1)
    =a1....ak(ak)
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Junior Member
    Joined
    Sep 2008
    Posts
    62
    suppose a,c are relatively prime. i.e. (a,c) = 1. also, a| bc ==> a p = bc for some integer p*. so, by Euclidean algorithm, there exists x and y integers such that 1 = ax+ cy
    multiplying b we get b = (ab)x + (bc)y
    ==> b = a(bx) + (ap)y by *
    ==> b = a(bx+py) .
    while b,x,p,y are integers we have bx+py is an integer and so, b is an integral mulple of a.
    ==> a | b.
    basing on this result, we go to the actual question.
    a1 | c , a2 |c , a1 and a2 are reletively prime.
    so, a1.a2 | c
    extending this property for n integers we get a1.a2.---.an | c.

    can i do it this way?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    Use the recommendation of Laurent.

    We just need to prove that if \gcd(a,b)=1 and a|c,b|c then ab|c.

    Since a|c,b|c it means aa'=c,bb'=c.

    Now \gcd(a,b)=1\implies 1 = ax+by \implies c = acx+bcy \implies c = abb'cx+aa'bcy.

    Factor out ab to complete the proof.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Junior Member
    Joined
    Sep 2008
    Posts
    62
    Quote Originally Posted by ThePerfectHacker View Post
    Use the recommendation of Laurent.

    We just need to prove that if \gcd(a,b)=1 and a|c,b|c then ab|c.

    Since a|c,b|c it means aa'=c,bb'=c.

    Now \gcd(a,b)=1\implies 1 = ax+by \implies c = acx+bcy \implies c = abb'cx+aa'bcy.

    Factor out ab to complete the proof.
    I am really lost to what your trying to do. You say to use Laurent recommendation, but you use a different proof. I know how to do the proof you did as it was required for one of our hw problems, but i dont see how solves this question of mines. Also, does my proof in the early post work?
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. pairwise relatively prime
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: June 10th 2010, 08:58 AM
  2. Vertices pairwise in grid graph
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: December 13th 2009, 07:41 AM
  3. Pairwise non-isomorphic formality
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: November 29th 2009, 06:05 AM
  4. Pairwise Independence vs Idependence help
    Posted in the Advanced Statistics Forum
    Replies: 1
    Last Post: September 15th 2009, 02:50 PM
  5. pairwise relatively prime integers
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: July 17th 2006, 10:10 AM

Search Tags


/mathhelpforum @mathhelpforum