It is currently 25 Jun 2017, 21:07

### GMAT Club Daily Prep

#### Thank you for using the timer - this advanced tool can estimate your performance and suggest more practice questions. We have subscribed you to Daily Prep Questions via email.

Customized
for You

we will pick new questions that match your level based on your Timer History

Track

every week, we’ll send you an estimated GMAT score based on your performance

Practice
Pays

we will pick new questions that match your level based on your Timer History

# Events & Promotions

###### Events & Promotions in June
Open Detailed Calendar

# When S is divided by 5 remainder is 3, when it is divided by

Author Message
Senior Manager
Joined: 08 Aug 2005
Posts: 251
When S is divided by 5 remainder is 3, when it is divided by [#permalink]

### Show Tags

26 Apr 2006, 03:32
This topic is locked. If you want to discuss this question please re-post it in the respective forum.

When S is divided by 5 remainder is 3, when it is divided by 7, remainder is 4. If K+S is divisible by 35, what is the least possible value of K?
Director
Joined: 13 Nov 2003
Posts: 789
Location: BULGARIA

### Show Tags

26 Apr 2006, 03:50
Hallo,
S=5*Z+3
s=7*G+4
When both equations are used , i got Z=(7*G+1)/5 when G=2,Z=3 and S=18. If S+K is divisible by 35 then K=17
If it is not wrong
GMAT Club Legend
Joined: 07 Jul 2004
Posts: 5043
Location: Singapore

### Show Tags

26 Apr 2006, 04:15
S = 5A + 3
S = 7B + 4

K+S is a multiple of 35

5A+3 = 7B+4
5A-7B = 1

Only possible set A,B = 3,2

S = 18

18+K/35. SMallest value of k is 35-18 = 17
SVP
Joined: 24 Sep 2005
Posts: 1885

### Show Tags

26 Apr 2006, 04:23
getzgetzu wrote:
When S is divided by 5 remainder is 3, when it is divided by 7, remainder is 4. If K+S is divisible by 35, what is the least possible value of K?

Or by Chinese modulus theorem, we have, from what is provided,
S=35n +18 ( n is integer)
S+ K= 35n +18+ K, 35n is divisible by 35 ---> the least possible value of K= 17 so that S+ K= 35n + 35
VP
Joined: 29 Apr 2003
Posts: 1403

### Show Tags

26 Apr 2006, 04:39
Dude, where do I get some background theory on this Chinese Modulus theorem?
Manager
Joined: 11 Oct 2005
Posts: 94

### Show Tags

26 Apr 2006, 18:39
Yes please i'd like some info as well....
VP
Joined: 29 Apr 2003
Posts: 1403

### Show Tags

26 Apr 2006, 18:54
Ans: 35 -18..

Tried finding the rite value of S that gives the remainder of 3 and 4 when divided by 5, 7 resp.

Started with 30 + 3, 25 +3 , 20 +3, 15 +3!

15+3, ie 18 worked!

Hence K = 35 -18!
Manager
Joined: 13 Dec 2005
Posts: 224
Location: Milwaukee,WI

### Show Tags

26 Apr 2006, 18:56
Here u go .click on the link below to master chinese remainder theorem .

http://www.cut-the-knot.org/blue/chinese.shtml
VP
Joined: 29 Apr 2003
Posts: 1403

### Show Tags

26 Apr 2006, 19:16
Xie Xie
Danke, Thank you.. Merci!
Manager
Joined: 21 Mar 2006
Posts: 89

### Show Tags

26 Apr 2006, 20:25
Quote:
Ans: 35 -18..

Tried finding the rite value of S that gives the remainder of 3 and 4 when divided by 5, 7 resp.

Started with 30 + 3, 25 +3 , 20 +3, 15 +3!

15+3, ie 18 worked!

Hence K = 35 -18!

I solved it the same way, sometimes simple logic is the efficient way to get to the answer.
VP
Joined: 28 Mar 2006
Posts: 1369

### Show Tags

27 Apr 2006, 04:31
ywilfred wrote:
S = 5A + 3
S = 7B + 4

K+S is a multiple of 35

5A+3 = 7B+4
5A-7B = 1

Only possible set A,B = 3,2

S = 18

18+K/35. SMallest value of k is 35-18 = 17

A=10,B=7 is another value
SVP
Joined: 24 Sep 2005
Posts: 1885

### Show Tags

27 Apr 2006, 04:35
The Chinese theorem works well with 2 facts relating to S but not with 3 facts.
VP
Joined: 28 Mar 2006
Posts: 1369

### Show Tags

27 Apr 2006, 04:37
laxieqv wrote:
getzgetzu wrote:
When S is divided by 5 remainder is 3, when it is divided by 7, remainder is 4. If K+S is divisible by 35, what is the least possible value of K?

Or by Chinese modulus theorem, we have, from what is provided,
S=35n +18 ( n is integer)
S+ K= 35n +18+ K, 35n is divisible by 35 ---> the least possible value of K= 17 so that S+ K= 35n + 35

Pls explain how you got the below stmt

S=35n +18 ( n is integer)
SVP
Joined: 24 Sep 2005
Posts: 1885

### Show Tags

27 Apr 2006, 04:49
trivikram wrote:
laxieqv wrote:
getzgetzu wrote:
When S is divided by 5 remainder is 3, when it is divided by 7, remainder is 4. If K+S is divisible by 35, what is the least possible value of K?

Or by Chinese modulus theorem, we have, from what is provided,
S=35n +18 ( n is integer)
S+ K= 35n +18+ K, 35n is divisible by 35 ---> the least possible value of K= 17 so that S+ K= 35n + 35

Pls explain how you got the below stmt

S=35n +18 ( n is integer)

We have:
S= 3(mod 5) or S= 4(mod 7)
S= 5m+ 3 ( m is integer) --> 5m+3= 4 ( mod 7) --> 5m= 1(mod 7) --> m= 3 ( mod 7 ) (the method is to try different remainders of 7, starting from 1) --> m= 7n + 3 ( n is integer) --> substitute m by n, we have:
S= 35n+ 18

The above method is so-called Chinese modulus theorem . I saw some above post have the link to this theorem.
GMAT Club Legend
Joined: 07 Jul 2004
Posts: 5043
Location: Singapore

### Show Tags

27 Apr 2006, 06:25
laxieqv wrote:
trivikram wrote:
laxieqv wrote:
getzgetzu wrote:
When S is divided by 5 remainder is 3, when it is divided by 7, remainder is 4. If K+S is divisible by 35, what is the least possible value of K?

Or by Chinese modulus theorem, we have, from what is provided,
S=35n +18 ( n is integer)
S+ K= 35n +18+ K, 35n is divisible by 35 ---> the least possible value of K= 17 so that S+ K= 35n + 35

Pls explain how you got the below stmt

S=35n +18 ( n is integer)

We have:
S= 3(mod 5) or S= 4(mod 7)
S= 5m+ 3 ( m is integer) --> 5m+3= 4 ( mod 7) --> 5m= 1(mod 7) --> m= 3 ( mod 7 ) (the method is to try different remainders of 7, starting from 1) --> m= 7n + 3 ( n is integer) --> substitute m by n, we have:
S= 35n+ 18

The above method is so-called Chinese modulus theorem . I saw some above post have the link to this theorem.

I like to add that the CRT works only if the mod values are relatively prime.

For three facts relating to S, I think it can be worked out but would require a very exhaustive method that invovles euclidean algorithm...

Here's a link, that shows how to solve for 3 facts using the CRT.

http://mathforum.org/library/drmath/view/56010.html

Last edited by ywilfred on 27 Apr 2006, 08:01, edited 1 time in total.
GMAT Club Legend
Joined: 07 Jul 2004
Posts: 5043
Location: Singapore

### Show Tags

27 Apr 2006, 07:58
Just to share a method someone taught me when I was still new in GMATClub. I'm not sure the logic behind it, but it works all the time.

S = 5A+3
S = 7B+4

Make B = 0, then 7B+4 = 4

Substitute 4 to A, and S = 5A+3 = 23. Now check....

23/5 --> R3
23/7 --> R2 --> No good, change to value, 23+5 = 28.

28/5 --> R3
28/7 --> R0 --> No good. Try 23-5 = 18

18/5 --> R3
18/7 --> R4 ---> This is the value of S we need.

You can make A = 0 if you like. Then we'll have 5A+3 = 3, and S = 7B+4 = 25.

Again, we need to do a little trial and error, but the required value is seldom far off.

25/5 --> R0 ---> That's no good. Try 25-7 = 18 and we'll have the required value of S to proceed with this question.
Intern
Joined: 12 Mar 2006
Posts: 26

### Show Tags

27 Apr 2006, 08:44
I got an ans of 17 assuming K is always positive.
27 Apr 2006, 08:44
Display posts from previous: Sort by