Awesome q2a theme
0 votes
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?

in Numerical Ability by (699 points) | 28 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
+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.
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 03 - 09
  1. Mellophi

    98 Points

  2. Ashutosh777

    70 Points

  3. Kushagra गुप्ता

    12 Points

  4. srestha

    11 Points

  5. arjun12

    10 Points

  6. prakhar2810

    8 Points

  7. sdutta

    7 Points

  8. shivarajkumar

    6 Points

  9. kuldeep kumar07

    6 Points

  10. toppoavinash

    6 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. Mellophi

    104 Points

  2. Ashutosh777

    73 Points

  3. Shaik Masthan

    13 Points

  4. srestha

    13 Points

  5. Kushagra गुप्ता

    12 Points

  6. arjun12

    10 Points

  7. Unnayan kumar

    8 Points

  8. prakhar2810

    8 Points

  9. sdutta

    7 Points

  10. Sourav Kar

    7 Points

7,725 questions
1,826 answers
11,148 comments
95,095 users