# Find the number given its remainders

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$

Proof

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:
break
else:
ns.append(i)
ms.append(m)
print ns
print ms

• 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. – Marius Mar 30 '16 at 9:02
• I am trying to see if there is any pattern from brute forcing. I'm sorry I am no mathematician. – 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.

Partial.
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.