28 views

When a number is divided by 13 ,the remainder is 11.when the same number is divided by 17,the remainder is 9.what is the number?

How to solve this without trial and error?

| 28 views

+1 vote
I feel trial and error, with intuition is the best way to solve this in the exam.

However, a formal way I've seen a while ago in an aptitude book:

Let the number be $N$

$N = 11mod(13)$
$N = 9mod(17)$

You can deduce that the given number cannot go beyond the LCM of $13$ and $17 = 221$. Else the remainders would start repeating, and you wouldn't get the lowest possible solution.

Now examine the 2 congruencies individually. Start with the remainder in each case, and increase by 13 or 17. The problem is to find the first common element.

analysing $N =11mod(13)$, $N$ could be $11,24,37,50,63,76,89,102,115,128,141,154,...$

analysing $N = 9mod(17)$, $N$ could be $9,26,43,60,77,94,111,128, 145, 162,...$

So you could conclude that 128 is the smallest such number.

Clearly, our dirty shortcuts are better and more satisfying.
by (1.9k points)
selected by
+1
Side note - given 13 and 17 are both primes, I assume there is another way involving Fermat's Theorem and modular arithmetic. I can't think of it, however.