Linear Congruences

**Zalren** · June 26th 2011, 05:59 PM

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.

**abhishekkgp** · June 26th 2011, 07:06 PM

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.

**chisigma** · June 26th 2011, 09:28 PM

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$

Thread: Linear Congruences

LinkBack

Thread Tools

Display