2
$\begingroup$

Question is find the smallest natural number $x$ such that,

\begin{align} x &\equiv 1 \pmod 2 \\ x &\equiv 2 \pmod 3 \\ x &\equiv 3 \pmod 4\\ x &\equiv 4 \pmod 5\\ x &\equiv 5 \pmod 6\\ x &\equiv 6 \pmod 7\\ x &\equiv 7 \pmod 8\\ x &\equiv 8 \pmod 9\\ x &\equiv 9 \pmod {10}\\ x &\equiv 10 \pmod {11}\\ x &\equiv 11 \pmod {12}\\ x &\equiv 0 \pmod {13}\\ \end{align}

However when I use the proof of Chinese remainder theorem, I cannot even get over the first step where I must find inverse modulo: $$b_1 \frac{6227020800}{2}\equiv 1 \pmod 2$$ which I presume is $$0\cdot \frac{6227020800}{2} + 2\cdot 1 \equiv 1$$ hence 0?

I am somewhat confused. A friend did it using another method, but I would like to learn how to use the Chinese remainder theorem.

$$x\equiv a_1 b_1 \frac{M}{m_1} + \cdots + a_k b_k \frac{M}{m_k} \pmod M$$

$\endgroup$
7
  • 1
    $\begingroup$ Hint: $\ x\equiv -1\,$ mod $\,2,3,\ldots, 12\ $ iff their lcm divides $\,x+1\ \ $ $\endgroup$ Jan 26, 2019 at 18:38
  • $\begingroup$ "However when I use the proof of theorem, I cannot even get over the first step where I must find inverse modulo: $\frac M{m_1}=\frac{6227020800}2$" Could you write out what proof and why exactly you are finding it? It's not clear what you are trying to do. $\endgroup$
    – fleablood
    Jan 26, 2019 at 18:38
  • $\begingroup$ @fleablood mathworld.wolfram.com/ChineseRemainderTheorem.html $\endgroup$
    – cemsicles
    Jan 26, 2019 at 18:39
  • $\begingroup$ I know what the CRT theorem is. I'm asking YOU to explain why you are doing that as the first step and why. $\endgroup$
    – fleablood
    Jan 26, 2019 at 18:40
  • 1
    $\begingroup$ $-1\pmod 8*9*5*7*11$ and $0 \pmod 13$ so solve that. If you get a negative number just add $8*9*5*7*11*13$. $\endgroup$
    – fleablood
    Jan 26, 2019 at 18:56

2 Answers 2

2
$\begingroup$

The Chinese remainder theorem is about relatively prime modulos. Having all the modulos from $2$ to $13$ is redundant.

$x\equiv 1 \mod 2; x \equiv 3\mod 4; x\equiv 7\mod 8$ are redundant and can be replaced with just $x \equiv 7 \pmod 8$.

Assuming the question is legitimate, we need not consider any $x \equiv j \pmod {2^km}$ and have to consider only $x\equiv l\pmod m$

i.e., this question can be reduced to.

$x\equiv 7\pmod 8$

$x \equiv 8\pmod 9$

$x \equiv 4 \pmod 5$

$x \equiv 6\pmod 7$

$x \equiv 10 \pmod {11}$

$x \equiv 0 \pmod {13}$.

All the rest are redundant, as the solution to the above is unique.

Note the solution to all but $x \equiv 0 \pmod {13}$ is $x \equiv -1 \pmod n$ for $n = 8,9,5,7,11$ so

$x\equiv -1 \pmod{8*9*5*7*11=27720}$ and $x \equiv 0 \pmod {13}$.

So you need to solve. $x = 27720k -1 = 13m$

$27720 \equiv 4 \pmod {13}$

So $x \equiv 27720k - 1\equiv 0 \pmod {13}$

$\equiv 4k -1 \equiv 0 \pmod {13}$

So $4k \equiv 1 \pmod {13}$ so we just have to find the inverse of $4 \mod {13}$

And $4 \times 10 = 40 \equiv 1 \pmod{13}$ and so $k = 10$

and $x \equiv 277199 \pmod {27720*13}$

$\endgroup$
1
  • $\begingroup$ God, I feel like an absolute moron... thanks. $\endgroup$
    – cemsicles
    Jan 26, 2019 at 18:58
1
$\begingroup$

$2,3,\ldots,12\mid x+1\iff 27720\mid x+1$ since $27720$ is the lcm of the divisors.

So $\, 13n = x = 27720\,\color{#c00} k - 1\ $ so $\bmod 13\!:\,\ \color{#c00} k\equiv \dfrac{1}{27720}\equiv\dfrac{ -12}4\equiv -3\equiv \color{#c00}{10}$

hence $\, x = 22720(\color{#c00}{10}+13m)-1 = 277199 + 13\cdot 27720\,m$

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .