# Linear Congruences

• Jun 26th 2011, 06:59 PM
Zalren
Linear Congruences
Find the smallest integer $n, n > 2$, such that $2 | n, 3 | (n+1), 4 | (n+2), 5 | (n+3)$, and $6 | (n+4)$.

I know how to solve Linear Congruences and I can use the Chinese Remainder Theorem. Just not sure how to set this up as a system of linear congruences. Any help to start me off would be appreciated.
• Jun 26th 2011, 08:06 PM
abhishekkgp
Re: Linear Congruences
Quote:

Originally Posted by Zalren
Find the smallest integer $n, n > 2$, such that $2 | n, 3 | (n+1), 4 | (n+2), 5 | (n+3)$, and $6 | (n+4)$.

I know how to solve Linear Congruences and I can use the Chinese Remainder Theorem. Just not sure how to set this up as a system of linear congruences. Any help to start me off would be appreciated.

$n \equiv 0 \,(mod2), \, n+1 \equiv 0 \,(mod 3), \, n+2 \equiv 0 \,(mod4)$ etc.
• Jun 26th 2011, 10:28 PM
chisigma
Re: Linear Congruences
Quote:

Originally Posted by Zalren
Find the smallest integer $n, n > 2$, such that $2 | n, 3 | (n+1), 4 | (n+2), 5 | (n+3)$, and $6 | (n+4)$.

I know how to solve Linear Congruences and I can use the Chinese Remainder Theorem. Just not sure how to set this up as a system of linear congruences. Any help to start me off would be appreciated.

The numbers satisfying the requirements are the solutions of linear congruences system...

$n \equiv 0\ \text{mod}\ 2$ (1)

$n \equiv 2\ \text{mod}\ 3$ (2)

$n \equiv 2\ \text{mod}\ 4$ (3)

$n \equiv 2\ \text{mod}\ 5$ (4)

$n \equiv 2\ \text{mod}\ 6$ (5)

First consequence of the 'chinese remainder theorem' the system of congruences (1) and (2) and the congruence (5) are equivalent, so that only this remain. Second consequence of the same theorem is that the system of congruence (2) and (3) has only one solution $\text{mod}\ 12$ that is...

$n \equiv 2\ \text{mod}\ 12$ (6)

... and that result cancels (5). Third consequence of the same theorem is that the system of (4) and (6) has only one solution $\text{mod}\ 60$ that is...

$n \equiv 2\ \text{mod}\ 60$ (7)

... and that is the solution of the problem. The minimum number $n > 2$ satisfying the requirement is then $n=62$...

Kind regards

$\chi$ $\sigma$