Check out my blog post
http://gmatquant.blogspot.com/2010/11/integral-solutions-of-ax-by-c.html
in which I discussed in detail how find integral solutions of linear equations in 2 variables.
Once you know how to solve any such equation, you will know what I am talking about below:

4x -17y = 1
First solution: I check for y = 1. Do I have a multiple of 4 which is 1 greater than 17? Nope. I move on to y = 2. Do I have a multiple of 4 which is 1 greater than 34? Nope. What about if y = 3? 17y = 51 which is 1 less than 52 (4 x 13).

So first solution is x = 13 and y = 3
Next solution will be obtained by adding 17 to x and adding 4 to y.
Second solution is x = 30 and y = 7
Next solution will be obtained by adding 17 to x and adding 4 to y
Third solution is x = 47 and y = 11
and so on ...
There are infinite solutions but we have constraints.
x <= 1000 and x and y should be positive.

We have to find how many terms are there in the sequence 13, 30, 47, ... (terms less than 1000)
All numbers are of the form 13 + 17a.
You want to find the greatest such number less than 1000. Divide 1000 by 17. You get 14 remainder. So 986 (=17 x 58) is the greatest number less than 1000 divisible by 17. When you add 13 to it, you get 999. So 999 is the greatest number of this sequence.

In the first term in the sequence above, a = 0, in the last term, a = 58. Hence number of such solutions = 59.
_________________

4x-17y=1
y=(4x-1)/17

x has to be a positive integer such that 1<=x<=1000 & (4x-1) is a factor of 17 so that y is also a positive integer

So we need to know how many numbers in the set {3,7,11,15,....,3999} are divisible by 17

Lets try to observe the pattern
1. 3 mod 17 = 3
2. 7 mod 17 = 7
3. 11 mod 17 = 11
4. 15 mod 17 = 15
5. 19 mod 17 = 2
6. 23 mod 17 = 6
7. 27 mod 17 = 10
8. 31 mod 17 = 14
9. 35 mod 17 = 1
10. 39 mod 17 = 5
11. 43 mod 17 = 9
12. 47 mod 17 = 13
13. 51 mod 17 = 0
14. 55 mod 17 = 4
15. 59 mod 17 = 8
16. 63 mod 17 = 12
17. 67 mod 17 = 16
... and after this the remainders will repeat (this is no co-incidence that the cyclicity is also 17)

So the right choices are x=13,13+17,13+17+17,.....

The number of such numbers is 59 (highest one being 999)
_________________

Karishma, that was a very helpful blog post. Thank you!

The number of positive integers valued pairs (x, y) satisfying 4x -17y = 1 and x <= 1000 (x is less than or equal to 1000) is

(A) 59
(B) 57
(C) 55
(D) 58
(E) 60


x=(1+17y)/4......(1)
for x<1000 we have max value of y=235(a quick way for getting y=235 is just putting x=1000 in eq (1))

a note to make here that for (1+17Y) to be divisible by 4, Y should take only odd values

now if we look at pattern for different Y values for eq(1) to be divisible by 4
we find Y satisfying 3,7,11,15........
means for every 2 odds one is satisfying our condition.
So we need to find the half of total nos. of odds between our range 1 to 235(for x<1000)
We get 118 nos. of odd
and half of that is 118/2=59
Ans A.

We are asked to find integer solutions for x,y.

There is no need to apply Euclidian algorithm here, we can get particular solutions simply by plugging in some values.
As y reaches 3 we get:

y’ = 3 and x’ = 13. We need only to solve for x.

General solution for x will be:

x = x’ + bn = 13 + 17n

Hence lower limit for n is n ≥ 0.

Now we’ll find upper limit using given restriction x ≤ 1000. Plugging in general solution we’ll get:

13 + 17n ≤ 1000
17n ≤ 987
n ≤ 58

And our list of possible values of n has following representation:

0, 1,2, 3, ….. , 58

Total number of elements is 59.

I have found an absolutely elegant way to solve this type of problems :

The number of positive integers valued pairs (x, y) satisfying 4x -17y = 1 and x <= 1000 (x is less than or equal to 1000) is :

1. Take the equation and divide by 4(the lesser of the two linear coeffs), giving :
x - 4.25y = .25

2. Take fractions to one side and integers to another, e.g. -
x - 4y = (y + 1)/4
and equate it with a constant k, e.g. -
x - 4y = (y + 1)/4 = k

3. From the above equation we can derive :
y = 4k - 1 ......................(1)
x = 4y + k......................(2)
replace (1) in (2)
x = 17k - 4 ....................(3)

From (1) we can derive k > 0, since y is positive.
From (2) we get 17k - 4 <= 1000
or, 17k <= 1004
or, k <= 1004/17
or, k <= 59....

So k can take values from 1 to 59, and each value of K gives a distinct pair of (x,y). Hence answer is 59. :)

KarishmaB can you plase explainhow did you figure out that next solution will be obtained by adding 17 to x and adding 4 to y.?
thanks

Hello from the GMAT Club BumpBot!

Thanks to another GMAT Club member, I have just discovered this valuable topic, yet it had no discussion for over a year. I am now bumping it up - doing my job. I think you may find it valuable (esp those replies with Kudos).

Want to see all other topics I dig out? Follow me (click follow button on profile). You will receive a summary of all topics I bump in your profile area as well as via email.
_________________