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$
  • 1
    $\begingroup$ Hint: $\ x\equiv -1\,$ mod $\,2,3,\ldots, 12\ $ iff their lcm divides $\,x+1\ \ $ $\endgroup$ – Bill Dubuque Jan 26 '19 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 '19 at 18:38
  • $\begingroup$ @fleablood mathworld.wolfram.com/ChineseRemainderTheorem.html $\endgroup$ – C. Ekinci Jan 26 '19 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 '19 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 '19 at 18:56
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}$

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ God, I feel like an absolute moron... thanks. $\endgroup$ – C. Ekinci Jan 26 '19 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$

| cite | improve this answer | |
$\endgroup$

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.