Puzzling Stack Exchange is a question and answer site for those who create, solve, and study puzzles. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|improve this question
up vote 13 down vote accepted

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

share|improve this answer

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.

share|improve this answer

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
share|improve this answer
3  
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 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 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.

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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