Results 1 to 4 of 4

Math Help - Congrences

  1. #1
    Member
    Joined
    Mar 2007
    From
    England
    Posts
    104

    Congrences

    Could someone please explain to me how to do this question:

    3x=5(mod 7)
    The answer is 4 but I'm not sure how to get there.

    Help would be appreciated.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Moo
    Moo is offline
    A Cute Angle Moo's Avatar
    Joined
    Mar 2008
    From
    P(I'm here)=1/3, P(I'm there)=t+1/3
    Posts
    5,618
    Thanks
    6
    Hello,

    Quote Originally Posted by free_to_fly View Post
    Could someone please explain to me how to do this question:

    3x=5(mod 7)
    The answer is 4 but I'm not sure how to get there.

    Help would be appreciated.
    You have to perform a division :

    x=5 \cdot 3^{-1} \bmod 7

    But you have to calculate a=3^{-1}, which is a such that 3a=1 \bmod 7

    One can see that 15=3*5=1 \bmod 7

    So a=5 \bmod 7


    Therefore :

     3x=5 \bmod 7 \Longleftrightarrow \overbrace{3a}^{1}x=5a \bmod 7

    \implies x=5a \bmod 7 \implies x=25 \bmod 7 \implies x=4 \bmod 7
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Mar 2007
    From
    England
    Posts
    104
    Ok, I think I more or less follow the previous explanation, but for this question I'm a little confused still:
    Q: 6x=2 (mod 8)

     x=2 \cdot 6^{-1} \bmod 8

    but this cancels to:
    <br />
x=1 \cdot 3^{-1} \bmod 8 (not sure if I can cancel like that)
    So <br />
a=3^{-1}<br />
    <br />
3a=1 \bmod 8
    But 3*3=9=1 (mod 8) so
    <br />
a=3 \bmod 8<br />
    This gives x=3 (mod 8)
    I know the answer is suppose to be x=3(mod 8) please can you show me where I went wrong.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Moo
    Moo is offline
    A Cute Angle Moo's Avatar
    Joined
    Mar 2008
    From
    P(I'm here)=1/3, P(I'm there)=t+1/3
    Posts
    5,618
    Thanks
    6
    Yes, I forgot to mention it. There is an inverse if and only if they are coprime.

    What I mean is that a has an inverse modulo n, if and only if a and n are coprime.

    Why ?

    Here, 6x=2 \bmod 8

    Going back to the definition of the congruence, we have : 6x-2=8k, where k \in \mathbb{Z}.

    That is to say 3x-1=4k.
    So this is the same as 3x=1 \bmod 4.

    When there is a common factor in a=b \bmod n, divide a,b, and n by this factor.

    ---------------------------
    In a general case, how to find an inverse ?

    - observe : for example, what number is divisible by 3 and such that it is 1 added to a multiple of 4 ? Answer is 9. It's easy by trial and error when it's small number.

    - use the euclidian algorithm... I can give you links where I've done such things, or you can read that : Extended Euclidean algorithm - Wikipedia, the free encyclopedia

    Follow Math Help Forum on Facebook and Google+

Search Tags


/mathhelpforum @mathhelpforum