The number of positive integers valued pairs (x, y) satisfyi : Problem Solving (PS)

My Profile Logout

Test's Subscription Expires:

My Follow Feed Kudos My Error Log

Messages and Replies

Settings Mark All Read

See All

Applicant Notifications

Settings Mark All Read

See All

Global notifications

Settings Mark All Read

See All

The number of positive integers valued pairs (x, y) satisfyi

Sort by Date

Sort by Kudos

Author

Message

TAGS:

Hide Tags

Manager

Joined: 25 Jan 2010

Posts: 104

Location: Calicut, India

The number of positive integers valued pairs (x, y) satisfyi [#permalink]

Show Tags

13 Nov 2010, 12:15

00:00

Difficulty:

95% (hard)

Question Stats:

33% (03:12) correct

67% (02:53) wrong

based on 124 sessions

HideShow timer Statistics

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

Spoiler: OA

_________________

If u think this post is useful plz feed me with a kudo

Most Helpful Expert Reply

Veritas Prep GMAT Instructor

Joined: 16 Oct 2010

Posts: 8659

Location: Pune, India

Re: Equation # 1 [#permalink]

Show Tags

13 Nov 2010, 17:46

cleetus wrote:

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

Am not sure abt the answer. I guess answer is 59 or 58 ( A or D)

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.
_________________

[b]Karishma
Veritas Prep GMAT Instructor

Learn more about how Veritas Prep can help you achieve a great GMAT score by checking out their GMAT Prep Options >

General Discussion

Retired Moderator

Joined: 02 Sep 2010

Posts: 766

Location: London

Re: Equation # 1 [#permalink]

Show Tags

13 Nov 2010, 15:09

cleetus wrote:

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)
_________________

Math write-ups
1) Algebra-101 2) Sequences 3) Set combinatorics 4) 3-D geometry

My GMAT story

GMAT Club Premium Membership - big benefits and savings

Current Student

Joined: 31 Mar 2013

Posts: 66

Location: India

GPA: 3.02

Re: The number of positive integers valued pairs (x, y) satisfyi [#permalink]

Show Tags

13 Apr 2014, 06:58

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

Joined: 05 Mar 2015

Posts: 1004

The number of positive integers valued pairs (x, y) satisfyi [#permalink]

Show Tags

17 Jan 2016, 05:22

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.

Senior Manager

Joined: 13 Oct 2016

Posts: 367

GPA: 3.98

Re: The number of positive integers valued pairs (x, y) satisfyi [#permalink]

Show Tags

16 Nov 2016, 04:23

cleetus wrote:

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

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.

Intern

Joined: 06 Jul 2018

Posts: 1

Re: The number of positive integers valued pairs (x, y) satisfyi [#permalink]

Show Tags

01 Aug 2018, 00:41

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.