Find the number given its remainders

Question

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?

Answer 1

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$).

Answer 2

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.

Answer 3

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

Answer 4

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.

[edit]
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.

Answer 5

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.

Answer 6

The search space can be reduced to n = 6k+1.

n-1 must be a multiple of six, because

• n-1 must be even because m+3 and m+4 both divide n-1;
• n-1 must be a multiple of 3,, because one of m, m+1, or m+2 must be a multiple of 3 (and (n-7) % 3 ≡ (n-1) % 3)

---

A (much) more efficient search can be achieved by iterating over potential m rather than potential n.

Note that

• n-1 must be a multiple of r=lcm(m+1,m+3,m+4).
• the range of possible solutions is bounded by s=lcm(m,m+1,m+2,m+3,m+4); if a solution n exists for a given m, then n + k×s for all integers k must also be solutions.

It follows that at most m×(m+2) potential solutions k×r need be tested for each m. However since solutions are of the form k×r+1 and are bounded between 300 & 500, our search for k can iterate over just [ ⎡299/r⎤ ... ⎣499/r⎦ ]

m	r	s	kmin = ⎡299/r⎤	kmax = ⎣499/r⎦	k×r+1
6	630	2520	1	0	(none)
7	440	27720	1	1	441
8	396	3960	1	1	397
9	780	25740	1	0	(none)
10	2002	60060	1	0	(none)
11	420	60060	1	1	421

So in practice this approach can solve the problem after checking just two k×r+1 candidate values for remainder after division by m and m+2.

We can stop increasing m once we're satisfied that r>500 must apply to all larger m; a brute-force scan of 6≤m≤496 reveals that m>11 ⇒ lcm(m+1,m+3,m+4)>500.