# Help With Chinese Remainder Theorem Question

Consider the consecutive positive integers $m, m+1, m+2, m+3$. It's given that the consecutive odd positive integers, $n,n+2,n+4,n+6$, divide them respectively.
That is $n|m$, $n+2|m+1$, $n+4|m+2$, $n+6|m+3$.
We can deduce the system of following congruences:
$m\equiv0\ (mod\ n)$
$m\equiv{n+1}\ (mod\ n+2)$
$m\equiv{n+2}\ (mod\ n+4)$
$m\equiv{n+3}\ (mod\ n+6)$
Since $n$ is odd, $2,4,6$ do not divide $n,n+2,n+4,n+6$ and so the modulo taken are pairwise coprime. This means we can use the Chinese remainder theorem to determine all $m$ in the product of the modulo.
Namely, the theorum states the solution, $\alpha$, is as follows;
$\alpha\equiv(0).\left[(n+2)(n+4)(n+6)\right].\left[\overline{ (n+2)(n+4)(n+6)} (mod\ n)\right] + \left[(n)(n+4)(n+6)\right].\left[\overline{ (n)(n+4)(n+6)} (mod\ n+2)\right]+ \left[(n)(n+2)(n+6)\right].\left[\overline{ (n)(n+2)(n+6)} (mod\ n+4)\right]+ \left[(n)(n+2)(n+4)\right].\left[\overline{ (n)(n+2)(n+4)} (mod\ n+6)\right]\ (mod\ (n)(n+2)(n+4)(n+6)$
Where Overlined term denotes then multiplicatve inverse in the given modulo.
I have done questions like this before but not in the general case as here, how can I find the inverses, I've tried Euclid's Algorithm but can't make much progress, any help would be much appreciated.

• Euclid's algorithm is the right track. You just have to use it backwords. An example, let us invert $17$ modulo $37$ : We have $$37=2\cdot 17+3$$ $$17=5\cdot 3+2$$ $$3=2+1$$ , hence $$1=3-2=3-(17-5\cdot 3)=6\cdot 3-17=6\cdot (37-2\cdot 17)-17=6\cdot 37-13\cdot 17$$ – Peter Aug 8 '17 at 18:05
• This is called the "extended euclidean algorithm" – Peter Aug 8 '17 at 18:09