Awesome q2a theme
0 votes

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?

in Numerical Ability by (699 points) | 29 views

1 Answer

+1 vote
Best answer
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
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.
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
Top Users 2020 Aug 10 - 16
  1. Arkaprava

    560 Points

  2. jayeshasawa001

    315 Points

  3. SarathBaswa

    288 Points

  4. Ashutosh777

    128 Points

  5. toxicdesire

    53 Points

  6. shashankrustagi2021

    15 Points

  7. Nilabja Sarkar

    12 Points

  8. Mellophi

    11 Points

  9. premu

    10 Points

  10. phaneendrababu

    9 Points

Weekly Top User (excluding moderators) will get free access to GATE Overflow Test Series for GATE 2021
Welcome to GATE CSE Doubts, where you can ask questions and receive answers from other members of the community.
Top Users Aug 2020
  1. Arkaprava

    560 Points

  2. jayeshasawa001

    320 Points

  3. SarathBaswa

    288 Points

  4. Ashutosh777

    204 Points

  5. Mellophi

    161 Points

  6. toxicdesire

    53 Points

  7. anurag sharma

    49 Points

  8. shashankrustagi2021

    25 Points

  9. premu

    16 Points

  10. Shaik Masthan

    16 Points

7,792 questions
2,046 answers
95,121 users