Results 1 to 3 of 3

Math Help - Linear Congruences

  1. #1
    Junior Member
    Joined
    Feb 2010
    Posts
    45

    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.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member abhishekkgp's Avatar
    Joined
    Jan 2011
    From
    India
    Posts
    495
    Thanks
    1

    Re: Linear Congruences

    Quote Originally Posted by Zalren View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor chisigma's Avatar
    Joined
    Mar 2009
    From
    near Piacenza (Italy)
    Posts
    2,162
    Thanks
    5

    Re: Linear Congruences

    Quote Originally Posted by Zalren View Post
    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
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Question about Linear Congruences
    Posted in the Number Theory Forum
    Replies: 0
    Last Post: February 26th 2011, 11:09 AM
  2. Linear Congruences
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: November 19th 2009, 09:02 PM
  3. Linear Congruences
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: October 19th 2009, 10:33 PM
  4. linear congruences
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: September 23rd 2008, 09:27 PM
  5. linear congruences
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: August 14th 2008, 10:40 AM

/mathhelpforum @mathhelpforum