9
$\begingroup$

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?

$\endgroup$

6 Answers 6

17
$\begingroup$

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

$\endgroup$
6
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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
$\endgroup$
3
  • 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, 2016 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, 2016 at 9:08
  • $\begingroup$ Marius, you have to start at m=6, not 8, because it is dividing by (m+2), not m, that gives a remainder of 7. $\endgroup$
    – Florian F
    Feb 6, 2023 at 12:07
1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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