16 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?

ago | 16 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.
ago by (1.2k points)
selected ago 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.