2
$\begingroup$

If I have:
\begin{align*} N &\equiv 1 &\pmod{2}\\ N &\equiv 2 &\pmod{3}\\ N &\equiv 3 &\pmod{4}\\ &\vdots\\ N &\equiv n - 1 &\pmod{n} \end{align*} How could I solve for $N$? Is there any property relates to this problem?

Update
Base on Moron hint, we have:
\begin{align*} N + 1 &\equiv 0 &\pmod{2}\\ N + 1 &\equiv 0 &\pmod{3}\\ N + 1 &\equiv 0 &\pmod{4}\\ \vdots\\ N + 1 &\equiv 0 &\pmod{n} \end{align*} Hence, $$N + 1 \equiv 0 \pmod{\mathrm{lcm}(2\cdot 3\cdots n}$$

$$\therefore N + 1 = lcm(2.3.4...n) * k \text{ for some integers k } $$ $$\implies N = lcm(2.3.4...n) * k - 1$$

Does it look right?

Thanks,
Chan

  • 2
    $N = k \times \text{lcm}(1,2,\ldots,n)-1$ where $k \in \mathbb{Z}$2011-02-28
  • 2
    http://en.wikipedia.org/wiki/Chinese_remainder_theorem2011-02-28
  • 0
    @Sivaram Ambikasaran: Thanks, but could you explain how it works? I know there is a property for $\pmod{lcm}$, but in this case the right hand side parts are different. It goes from 1 -> n - 1.2011-02-28
  • 0
    @Qiaochu Yuan: Thanks for the link2011-02-28
  • 0
    @Chan: As Qiaochu points out this is nothing but a special case of Chinese Remainder Theorem. your $N \equiv -1 \bmod m$, $\forall m \in \{1,2,\ldots,n\}$2011-02-28
  • 0
    @Sivaram Ambikasaran: Thanks.2011-02-28
  • 0
    @Chan: Yes, the result is correct now.2011-02-28

1 Answers 1

4

Hint: Consider the possible values for $N+1$.

  • 0
    I got it ;) So simple. Many thanks.2011-02-28