Results 1 to 3 of 3

Math Help - Proof Help Needed

  1. #1
    Newbie
    Joined
    Sep 2012
    From
    United States
    Posts
    14

    Question Proof Help Needed

    If gcd(a,b)=1 and ax+by=c has a positive integer solution, then so does ax+by=d when d>c. I need help proving this. Thanks.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Sep 2012
    From
    Australia
    Posts
    3,619
    Thanks
    592

    Re: Proof Help Needed

    Hey clintonh0610.

    Its been a while since I've seen this, but my guess is to look at the conditions and procedures for solving a linear Diophantine equation and find the relationship between the gcd and the number of solutions.

    From my prior coursework in cryptography I do know there is a specific protocol for solving linear Diophantine equations but I can't remember exactly what is involved.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member
    Joined
    Dec 2012
    From
    Athens, OH, USA
    Posts
    633
    Thanks
    255

    Re: Proof Help Needed

    I'm not certain how to interpret your problem? Given a and b positive integers with gcd(a,b)=1. By a positive integer solution of ax + by = c, do you mean positive integers x and y with ax + by = c? If so, your assertion is false. Take a=3, b=5, c=8 and d=9. Clearly, ax+by=8 has solution x=y=1 but also clearly ax+by=9 has no positive integer solutions.

    So amend your assertion to non-negative solutions. Your assertion is still false. Again a=3, b=5, c=3 and d=4 is a counter example.

    A "standard" number theory exercise is:
    Let a and b be positive integers with gcd(a,b)=1. If d is any integer with d >= ab, then there are non_negative integers x and y with ax + by = d.

    Perhaps this is what you meant?
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. A proof is needed
    Posted in the Differential Geometry Forum
    Replies: 2
    Last Post: September 25th 2010, 03:59 PM
  2. A proof is needed
    Posted in the Geometry Forum
    Replies: 3
    Last Post: June 6th 2010, 02:39 AM
  3. 'Proof' help needed please...
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: February 27th 2010, 12:39 PM
  4. A much needed proof
    Posted in the Math Topics Forum
    Replies: 3
    Last Post: November 10th 2007, 10:05 AM
  5. help needed with a proof
    Posted in the Advanced Algebra Forum
    Replies: 2
    Last Post: November 27th 2006, 09:00 AM

Search Tags


/mathhelpforum @mathhelpforum