Results 1 to 4 of 4
Like Tree2Thanks
  • 1 Post By Soroban
  • 1 Post By Deveno

Math Help - Linear congruence

  1. #1
    Newbie
    Joined
    Nov 2012
    From
    New York
    Posts
    10

    Linear congruence

    Hi, this is my first post, I'm having problems with this

    Solve the linear congruence 35x ≡ 47 (mod 24)

    I'm a little confused with simplification, tnks.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member

    Joined
    May 2006
    From
    Lexington, MA (USA)
    Posts
    11,707
    Thanks
    627

    Re: Linear congruence

    Hello, frankitm!

    Welcome aboard!
    I have a solution using "ordinary" algebra.


    \text{Solve the linear congruence: }\:35x \:\equiv\:47\text{ (mod 24)}

    Since 35 \equiv 11\text{ (mod 24)} and 47 \equiv 23\text{ (mod 24)}

    . . the equation becomes: . 11x\,\equiv\,23\text{ (mod 24)}

    This means: . 11x \:=\:24a + 23 for some integer a.

    Solve for x\!:\;x \:=\:\frac{24a+23}{11} \quad\Rightarrow\quad x \:=\:2a + 2 + \frac{2a+1}{11} .[1]

    Since x is an integer, 2a+1 must be a multiple of 11.
    . . The first time this happens is: a = 5

    Substitute into [1]: . x \:=\:2(5) + 2 + \frac{2(5)+1}{11}

    Therefore: .  x \:=\:13
    Last edited by Soroban; November 6th 2012 at 09:32 PM.
    Thanks from topsquark
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Nov 2012
    From
    New York
    Posts
    10

    Re: Linear congruence

    Thank you Soroban =)
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,370
    Thanks
    739

    Re: Linear congruence

    suppose we knew that there was some "magic" integer k such that:

    35k = 1 (mod 24)

    then from 35x = 47 (mod 24) we could deduce:

    k(35x) = 47k (mod 24)

    (35k)x = 47k (mod 24)

    1x = 47k (mod 24)

    x = 47k (mod 24).

    so what could this "magic number" k be?

    well, as it turns out: gcd(35,24) = 1. this means that there are INTEGERS a,b with 35a + 24b = 1 (this is called Bezout's identity).

    if we take both sides mod 24, we get:

    35a = 1 (mod 24), so "a" would be the "k" we were looking for!

    we can, in fact, do a little better:

    35 = 11 (mod 24) which means:

    35 = 11 + 24n (for n = 1, in fact)

    thus 35k = (11 + 24)k = 11k + 24k, so 35k = 11k (mod 24).

    11 is a smaller number to work with than 35, so we're actually looking for an a and b with:

    11a + 24b = 1.

    here's how we find a:

    24 = 2*11 + 2
    11 = 5*2 + 1 <--gcd right here!

    so 1 = 11 - (5*2), and 2 = 24 - (2*11), so:

    1 = 11 - 5*(24 - 2*11) = 11 - 5*24 + 10*11 = 11*11 + (-5)*24. so a = 11, and b = -5 (but we don't need b now. goodbye!).

    this means that 11*11 = 1 (mod 24) (and indeed, 121 is in fact congruent to 1 mod 24, since 121 = 5*24 + 1).

    we can also do a little better on the right-hand side of the congruence, since 47 = 23 (mod 24).

    so instead of solving 35x = 47 (mod 24), we can solve the slightly easier problem:

    11x = 23 (mod 24).

    and, just as above, multiplying both sides by 11 (mod 24), we get:

    x = 23*11 (mod 24).

    now 23*11 = 253 = 13 + 240 = 13 + 10*24, so x = 13 (mod 24).

    does this work?

    let x = 13 + 24n (where n might be ANY integer).

    then 35x = 35(13 + 24n) = 455 + 840n = 47 + 408 + 840n = 47 + 24(17 + 35n).

    since 17 + 35n is surely an integer when n is, we conclude when x = 13 + 24n,

    then 35x = 47 + 24k, where k = 17 + 35n, that is:

    35x = 47 (mod 24).
    Thanks from frankitm
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Linear Congruence
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: February 24th 2010, 05:11 AM
  2. Solving a linear congruence
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: November 29th 2009, 06:54 PM
  3. non-linear congruence proof
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: November 8th 2009, 01:05 PM
  4. Linear congruence
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: July 1st 2009, 05:48 AM
  5. Linear Congruence
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: June 3rd 2008, 10:04 AM

Search Tags


/mathhelpforum @mathhelpforum