I am wondering if there is a structured way to solve this kind of problem:

There is a number $n$

  • $n$ divided by $m$ (m is not given) has remainder 5
  • $n$ divided by $m+1$ has remainder 1
  • $n$ divided by $m+2$ has remainder 7
  • $n$ divided by $m+3$ has remainder 1
  • $n$ divided by $m+4$ has remainder 1
  • $n$ is between 300 and 500

and (only use it if you really need them):

  • $n$ divided by $m+5$ has remainder 7
  • $n$ divided by $m+6$ has remainder 5

There is (at least one) solution to this puzzle, I am not sure if there are more than one. but how to find it?

From the given, can I deduce that $n$ is odd?

But is there more to know about $n$ and are there ways to find $n$ that do not rely on brute force?


I believe the only solution is

$n=397$, $m=8$


Consider the number $n-1$. This is divisible by $m+3$ and $m+4$.
These numbers are coprime if $m+3 > 1$ and, in this case, $n-1$ is divisible by $(m+3)(m+4)$. But $22*23 > 500$ so $m+3<22$ i.e, $m<19$.

It is also the case that $n-1$ is divisible by $m+1$ and gcd$(m+1, m+3) \le 2$ and gcd$(m+1, m+4) \le 3$ so that $n-1 \ge \frac{m+1}{6}(m+3)(m+4)$
From this inequality, we find that $n < 500$ only if $m < 12$.

Since $n$ divided by $m$ has remainder $5$ we must presume that $5 <m$ and so $5 < m < 12$ i.e, $6$ possibilities.

$m=6 \Rightarrow m+1 = 7$ and then $n-1$ must be divisible by $7*9*10 > 500$
$m=7 \Rightarrow m+1 = 8$ and then $n-1$ is divisible by at least $4*10*11 = 440 \Rightarrow n=441$.
$m=8 \Rightarrow m+1 = 9$ and then $n-1$ is divisible by $3*11*12 = 396 \Rightarrow n=397$ .
$m=9 \Rightarrow m+1 = 10$ and then $n-1$ is divisible by $5*12*13 >500$
$m=10 \Rightarrow m+1 = 11$ and then $n-1$ is divisible by $11*13*14 >500$
$m=11 \Rightarrow m+1 = 12$ and then $n-1$ is divisible by $2*14*15 =420 \Rightarrow n=421$

Hence there are just three cases to check $n=441, 397$ and $421$ and only $n=397$ works in which case $m=8$ (in fact $397$ is the only one that leaves remainder $5$ when divided by the corresponding $m$).


Easy proof that n is odd:

n has an odd remainder when divided by both m and m+1.
One of m and m+1 is even.
n has an odd remainder when divided by an even number.
n must be odd.


Using brute force I found that

n = 397, when m = 8

begin = 300
end = 500
pairs = {0:5, 1:1, 2:7, 3:1, 4:1, 5:7, 6:5}
ns = []
ms = []
for i in xrange(begin, end + 1):
    for m in xrange(1, 1000):
        for k, v in pairs.items():
            if i % (m + k) != v:
print ns
print ms
  • 3
    $\begingroup$ First off all the OP asks about a method that does not involve brute force. Second, why do you search for m between 1 and 1000? You can start with 8 (since the biggest reminder is 7) and stop at n-1since m < n. $\endgroup$ – Marius Mar 30 '16 at 9:02
  • $\begingroup$ I am trying to see if there is any pattern from brute forcing. I'm sorry I am no mathematician. $\endgroup$ – nieylarm Mar 30 '16 at 9:08

In general it cannot be solved. Given one remainder we have three unknowns: m, the number we must multiply m by to get it within m of n and n itself. With each remainder we add adds another unknown (the number we must multiply m+1 by to get within m+1 of n). Therefore we will always have 2 more unknowns than we have equations.

Another way you can think about it is there are infinite possible values of n and each remainder we are given we reduce this number by factor of m+x, sadly that still gives us infinite possible values of n.

Whilst you will always be able to find solutions to n there will always be infinite correct solutions to n unless provided with two other bounding conditions. i.e. x < n < y as has been done and solved for in other answers.


I can only prove that n is odd for now.

$n = m*k + 5$
If m is even then n is odd because the line above can be written as
$n = 2*a *k + 5$ or $n = 2*(a*k+2) + 1$ which is odd.
if m is odd then we move to the next one
$n=(m+1)*k + 1$ (different k as the one above).
This can be written as
$n=(2*a+1+1)*k + 1$ or $n = 2*(a+1)*k+1$ so n is an odd number.

An easier proof that n is odd:

$m+3$ divides $n-1$ and $m+4$ divides $n-1$.
this means that
$n-1 = (m+3)*(m+4)$.
the product of 2 consecutive numbers is an even number so
$n-1 = 2*k$ which results in $n = 2*k+1$

Working on the rest.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.