The Math Forum

Ask Dr. Math - Questions and Answers from our Archives
Associated Topics || Dr. Math Home || Search Dr. Math

Diophantine equations in Number Theory

Date: 01/24/2001 at 14:51:39
From: Kristi Harp
Subject: Diophantine equations in number theory

Here is the problem: 

If a and b are relatively prime positive integers, prove that the 
Diophantine equation ax-by = c has infinitely many solutions in the 
positive integers. 

[Hint: There exist integers x0 and y0 such that ax0+by0 = c. For any 
integer t, which is larger that both |x0|/b and |y0|/a, a positive 
solution of the given equation is x = x0+bt, y = -(y0-at).] 

(Note: x0 is x null or naught...I didn't know how else to write it.)

I'm stuck on this homework problem. If anyone can please help me I 
would greatly appreciate it. Thank you.

Date: 01/24/2001 at 19:35:01
From: Doctor Anthony
Subject: Re: Diophantine equations in number theory

If a and b are coprime you can always find integers p, q such that

   ap + bq = 1  using Euclid's algorithm.

Then multiply by c to get

     ax' + by' = c ......(1)  where  x' = cp,  y' = cq

and finally let x = x'+bt   y = -(y'-at)  and substituting into the 

                ax - by = c  we get

     a(x'+bt) +b(y'-at) = c

  ax' + abt + by' - abt = c

              ax' + by' = c    which we have shown from (1) is true.

It follows that there are an infinity of solutions of the form

    x = x'+bt     y = -(y'-at)   where  ax'+by'=c
- Doctor Anthony, The Math Forum   
Associated Topics:
High School Linear Equations
High School Number Theory

Search the Dr. Math Library:

Find items containing (put spaces between keywords):
Click only once for faster results:

[ Choose "whole words" when searching for a word like age.]

all keywords, in any order at least one, that exact phrase
parts of words whole words

Submit your own question to Dr. Math

[Privacy Policy] [Terms of Use]

Math Forum Home || Math Library || Quick Reference || Math Forum Search

Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.