Number Prop

[yellowho]

When positive integer n is divided by 5, the remainder is 1, when n is divided by 7, the remainder is 3. What is the smallest positive integer k such that k+n is a multiple of 35?

[AIM GMAT]

When positive integer n is divided by 5, the remainder is 1, when n is divided by 7, the remainder is 3. What is the smallest positive integer k such that k+n is a multiple of 35?

The answer would be 4 .

n = 31 k = 4

n + k = 35

n for 5 giving remainder 1 = [6,11,16,21,26,31,36,41,46,51]
n for 7 giving remainder 3 = [10,17,24,31,38,45,52,59,66,73]

Smallest number common between both sets is 31 .


31/5 gives remainder 1 and 31/7 gives remainder 3 .

[rohu27]

not sure but is it 4?

[yellowho]

yeah. my way: (testing number)

0 is the first multiple of 35; can't come up with a k and n to satisfy
next 35, works.

I guess we got lucky here is there a "better" way to do this? Perhaps the experts on modulus can chime in.

[rohu27]

k+n is a multiple of 35 - so it an be 35,70 etc
if it is 35, then n shud be 31 to satify the remainders of both 5 and 7. 31+4=35, so k=4
same wth 70. n shud be 66, here too k=4.

this is how i did it. ya but the 0 one doesnt work out though.

yeah. my way: (testing number)

0 is the first multiple of 35; can't come up with a k and n to satisfy
next 35, works.

I guess we got lucky here is there a "better" way to do this? Perhaps the experts on modulus can chime in.

[Anurag@Gurome]

When positive integer n is divided by 5, the remainder is 1, when n is divided by 7, the remainder is 3. What is the smallest positive integer k such that k+n is a multiple of 35?

Just note that (n + 4) is multiple of both 5 and 7.
Smallest possible value of (n + 4) is 35 (zero is discarded as that would make n negative)

Therefore, smallest possible value of k is nothing but 4.