Results 1 to 9 of 9

Math Help - Congruence

  1. #1
    MHF Contributor
    Joined
    Mar 2010
    From
    Florida
    Posts
    3,093
    Thanks
    5

    Congruence

    Find the in-congruent solutions to 49x\equiv 22 \ \mbox{(mod 36)}

    gcd(36,49)=1
    49=36*1+13
    36=13*2+10
    13=10*1+3
    10=3*3+1
    3=1*3+0
    Working backwards I obtain: 1=36*15-49*11

    -11\equiv y \ \mobx{(mod 36)}\rightarrow -11\equiv 25 \ \mbox{(mod 36)}

    x\equiv 22*25 \ \mbox{(mod 36)}\rightarrow x\equiv 10 \ \mbox{(mod 36)}

    x_0=10

    x=10+36t \ 0\leq t<1
    x=10 \ \mbox{is the in-congruent solution}

    Is this correct and if so, is there an easier way to do this?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Apr 2005
    Posts
    14,973
    Thanks
    1121
    It is easy to see that it works: 49*10= 490 and 490/36= 13 with remainder 22.

    As for an "easier way", what you did looks pretty easy to me! Certainly better than multiplying 48 by 1, 2, 3, etc. until you find the right one.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor
    Joined
    Mar 2010
    From
    Florida
    Posts
    3,093
    Thanks
    5
    Quote Originally Posted by HallsofIvy View Post
    It is easy to see that it works: 49*10= 490 and 490/36= 13 with remainder 22.

    As for an "easier way", what you did looks pretty easy to me! Certainly better than multiplying 48 by 1, 2, 3, etc. until you find the right one.
    Maybe easy is the wrong word. Is there a more efficient way?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor Also sprach Zarathustra's Avatar
    Joined
    Dec 2009
    From
    Russia
    Posts
    1,506
    Thanks
    1
    Maybe...

    49x=22(mod 36)

    ==>

    49x+14=36=0 (mod36)

    ==>

    7(7x+2)=0(mod36)

    now it's clear that x=10
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Member
    Joined
    Jun 2010
    From
    Israel
    Posts
    148
    Quote Originally Posted by dwsmith View Post
    Find the in-congruent solutions to 49x\equiv 22 \ \mbox{(mod 36)}

    gcd(36,49)=1
    49=36*1+13
    36=13*2+10
    13=10*1+3
    10=3*3+1
    3=1*3+0
    Working backwards I obtain: 1=36*15-49*11

    -11\equiv y \ \mobx{(mod 36)}\rightarrow -11\equiv 25 \ \mbox{(mod 36)}

    x\equiv 22*25 \ \mbox{(mod 36)}\rightarrow x\equiv 10 \ \mbox{(mod 36)}

    x_0=10

    x=10+36t \ 0\leq t<1
    x=10 \ \mbox{is the in-congruent solution}

    Is this correct and if so, is there an easier way to do this?
    In general, the congruence ax\equiv b(mod\ n) has solutions if and only if gcd(a,n)|b. In case solutions exist, there are exactly gcd(a,n) incongruent solutions modulo n .


    49x\equiv 22\equiv -14(mod\ 36) and since gcd(7,36)=1 you can cancel without affecting the modulus, then 7x\equiv -2(mod\  36); multiply by -5 , then -35x\equiv 10(mod 36); and the unique solution is x\equiv 10(mod\ 36).
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor Also sprach Zarathustra's Avatar
    Joined
    Dec 2009
    From
    Russia
    Posts
    1,506
    Thanks
    1
    This is "my solution"
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Member
    Joined
    Jun 2010
    From
    Israel
    Posts
    148
    Quote Originally Posted by Also sprach Zarathustra View Post
    This is "my solution"
    That's wonderful.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Super Member

    Joined
    May 2006
    From
    Lexington, MA (USA)
    Posts
    11,547
    Thanks
    539
    Hello, dwsmith!

    Here is a very primitive solution . . .


    Solve:. . 49x \:\equiv\: 22 \text{ (mod 36)}

    The congruence reduces to: . 13x \:\equiv\:22\text{ (mod 36)}

    This means: . 13x \:=\:36a + 22\,\text{ for some integer }a.

    \text{Solve for }x\!:\;\;x \:=\:\dfrac{36a + 22}{13} \:=\:2a + 1 + \dfrac{10a + 9}{13} .[1]

    Since x is an integer, 10a + 9 must be divisible by 13.

    We have: . 10a + 9 \:=\:13b\,\text{ for some integer } b.

    \text{Solve for }a\!:\;\;a \:=\:\dfrac{13b - 9}{10} \:=\:b + \dfrac{3b-9}{10} .[2]

    Since a is an integer, 3b-9 must be divisible by 10.

    The first time this happens is when b = 3.


    Substitute into [2]: . a \:=\:3 + \frac{3(3)-9}{10} \quad\Rightarrow\quad a = 3

    Substitute into [1]: . x \;=\;2(3)+1 + \frac{10(3) + 9}{13} \quad\Rightarrow\quad x \:=\:10


    Therefore: . x \:\equiv\:10\text{ (mod 36)}
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Super Member
    Joined
    Jan 2009
    Posts
    715
    Or how about this ?

     13x \equiv 2 \cdot 11 \bmod{36}

     x \equiv 2 ~ \frac{ a - 1 }{a+1} ~~,~ a \equiv 12

     x \equiv 2  (a-1)( 1 - a + a^2 - a^3  + ... )

    I don't consider the convergence of the series because we find that  a^n \equiv 0 ~,~ n \geq 2

     x \equiv 2(a-1)(1-a) \equiv 2( -a^2 + 2a - 1 ) \equiv 2(2a - 1 ) \equiv 2(23) \equiv 10
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Congruence
    Posted in the Number Theory Forum
    Replies: 7
    Last Post: May 12th 2009, 10:19 AM
  2. Congruence
    Posted in the Geometry Forum
    Replies: 1
    Last Post: November 10th 2008, 01:52 PM
  3. congruence
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: September 30th 2008, 05:04 PM
  4. Congruence
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: September 30th 2008, 09:11 AM
  5. Congruence
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: September 29th 2008, 10:57 AM

Search Tags


/mathhelpforum @mathhelpforum