Consecutive positive integers $m$, $m+1$, $m+2$ and $m+3$ are divisible by consecutive odd positive integers $n$, $n+ 2$, $n+ 4$ and $n+ 6$ respectively. Determine the smallest possible $m$ in terms of $n$.

So, I already tried solving this using the fact that this is a system of linear congruences. We have:

$$m\equiv 0 \pmod{n}$$ $$m+1 \equiv 0 \pmod{n + 2}$$ $$m+2 \equiv 0 \pmod{n + 4}$$ $$m+3 \equiv 0 \pmod{n + 6}$$

My approach revolved around this:

From the first congruence, we know that $$m=nk$$ where $k$ is an integer. Then we take this and substitute it into the second congruence: $$ nk+1 \equiv 0 \pmod{n + 2}$$

And then solve for $k$, introduce a new variable, and substitute it back to the original equation for $m$. Needless to say, this approach gets extremely long and ugly. My teacher told me there is a way to do this problem using the Chinese Remainder theorem, however how do we prove that $n$, $n+2$, $n+4$ and $n+6$ are pairwise relatively prime?

  • 1
    $\begingroup$ $n,n+2,n+4,n+6$ might not be pairwise coprime. Indeed, if $n$ is divisibile by $3$, then so is $n+6$. But, apart from this exception, these are actually coprime. That's because every common prime divisor should divide their difference as well: this may be $2,4$ or $6$. But these are odd numbers, hence only $3$ may be a common divisor. $\endgroup$ – Crostul Dec 5 '16 at 23:55
  • $\begingroup$ So the approach may be to take three of the congruences and apply the CRT to them? $\endgroup$ – user14513462563 Dec 6 '16 at 5:24

Here are some hints.

Begin by showing that, for $n$ relatively prime to $3$, that $$ m=\frac{n(n+2)(n+4)(n+6)+n}{2} $$ works, and for $n$ divisible by $3$, that $$ m=\frac{n(n+2)(n+4)(n+6)+3n}{6} $$ works.

Then use the Chinese Remainder Theorem to argue that no smaller $m$ will do.


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.