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 repost 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

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

S = 5A + 3
S = 7B + 4
K+S is a multiple of 35
5A+3 = 7B+4
5A7B = 1
Only possible set A,B = 3,2
S = 18
18+K/35. SMallest value of k is 3518 = 17



SVP
Joined: 24 Sep 2005
Posts: 1885

Re: Remainder [#permalink]
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

Dude, where do I get some background theory on this Chinese Modulus theorem?



Manager
Joined: 11 Oct 2005
Posts: 94

Yes please i'd like some info as well....



VP
Joined: 29 Apr 2003
Posts: 1403

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

Here u go .click on the link below to master chinese remainder theorem .
http://www.cuttheknot.org/blue/chinese.shtml



VP
Joined: 29 Apr 2003
Posts: 1403

Xie Xie
Danke, Thank you.. Merci!



Manager
Joined: 21 Mar 2006
Posts: 89

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

ywilfred wrote: S = 5A + 3 S = 7B + 4
K+S is a multiple of 35
5A+3 = 7B+4 5A7B = 1
Only possible set A,B = 3,2
S = 18
18+K/35. SMallest value of k is 3518 = 17
A=10,B=7 is another value



SVP
Joined: 24 Sep 2005
Posts: 1885

The Chinese theorem works well with 2 facts relating to S but not with 3 facts.



VP
Joined: 28 Mar 2006
Posts: 1369

Re: Remainder [#permalink]
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

Re: Remainder [#permalink]
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 socalled 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

Re: Remainder [#permalink]
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 socalled 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

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 235 = 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 257 = 18 and we'll have the required value of S to proceed with this question.



Intern
Joined: 12 Mar 2006
Posts: 26

I got an ans of 17 assuming K is always positive.










