division by 30

[GmatKiss]

Positive integer n leaves a remainder of 4 after division by 6 and a remainder of 3 after division by 5. If n is greater than 30, what is the remainder that n leaves after division by 30?

(A) 3
(B) 12
(C) 18
(D) 22
(E) 28

IMO:E

[Anurag@Gurome]

Positive integer n leaves a remainder of 4 after division by 6 and a remainder of 3 after division by 5. If n is greater than 30, what is the remainder that n leaves after division by 30?

Method 1 : Plugging the options
Option A : Leaves a remainder of 3 when divided by 6 --> NO
Option B : Leaves a remainder of 0 when divided by 6 --> NO
Option C : Leaves a remainder of 0 when divided by 6 --> NO
Option D : Leaves a remainder of 2 when divided by 5 --> NO
Option E : Must be the correct option.

The correct answer is E.

[Anurag@Gurome]

Positive integer n leaves a remainder of 4 after division by 6 and a remainder of 3 after division by 5. If n is greater than 30, what is the remainder that n leaves after division by 30?

Method 2 : Listing the numbers
remainder of 4 after division by 6 : 4, 10, 16, 22, 28, 34...
remainder of 3 after division by 5 : 3, 8, 13, 18, 23, 28...

28 is common in both the lists.

The correct answer is E.

[Anurag@Gurome]

Positive integer n leaves a remainder of 4 after division by 6 and a remainder of 3 after division by 5. If n is greater than 30, what is the remainder that n leaves after division by 30?

Method 3 : Tricky Algebra
Note that (n + 2) is divisible by both 5 and 6.
Hence, (n + 2) must be a multiple of LCM(5, 6) = 30

Therefore, possible values of n are : 28, 58, 88 etc

The correct answer is E.

[Anurag@Gurome]

Positive integer n leaves a remainder of 4 after division by 6 and a remainder of 3 after division by 5. If n is greater than 30, what is the remainder that n leaves after division by 30?

Method 4 : Algebra (Generalized Method)
n can be written as (6a + 4) and (5b + 3), where a and b are non-negative integers.

Hence, (6a + 4) = (5b + 3) ---> 5b = (6a + 1) = 5a + (a + 1)
Hence, (a + 1) must be divisible by 5 too.
Thus, possible values of a are : 4, 9, 14 etc

Therefore, possible values of n are : 28, 58, 88 etc.

The correct answer is E.

[moonraker]

Another method can be using an example:
Lets say n = 6a + 4 = 5b+ 3

Solving the a and b equations we case see that : 6a + 4 = 5b+3 => 6a + 1 = 5b
now for LHS to be a multiple of 5 the only options for 6a are those multiples ending with 4 and not 9 (no multiple of 6 will ever end with 9).

For the number to be greater than 30 the first multiple ending with 4 for 6a = 54 (6 x9) ........... (later on u can take 6x14 or 6x19 and so on)

hence the number would be 6x9 + 4 = 58.........
Divide this by 30 and you get the remainder 28....

Answer is thus E