Results 1 to 6 of 6

Math Help - Cant work out how someone goes from one step to next in short mod arithmetic problem

  1. #1
    Member
    Joined
    Mar 2009
    Posts
    182
    Thanks
    1

    Cant work out how someone goes from one step to next in short mod arithmetic problem

    Ok so we have:

    3+4s=1(mod5)
    4s=3(mod5)

    from there to there is fine obviously, but then after they do this....

    4*4s=4*3(mod5)
    s=2(mod5)

    Can someone explain simply what is going on to get to s=2(mod5)

    Thanks!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,317
    Thanks
    697
    mod 5 every non-zero element has a multiplicative inverse. for example (4)(4) = 1 mod 5, so "1/4" = 4.

    thus s = 1s = ((4)(4))s = 4(4s).

    the RHS (4)(3) = 2 mod 5 should be clear, since 12 = 2 mod 5.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Mar 2009
    Posts
    182
    Thanks
    1
    thanks, that makes sense, so what now if i have:
    n*s = 2a(mod2n)
    so, n*s = a(mod2n)?

    how would i proceed from here.... because i cant find the multiplicative inverse this time can i?

    Basically this is in the midst of solving the simultaneous congruences:

    x = a(modn)
    x = 2a(mod2n)
    x = 3a(mod3n)

    So im trying to use the chinese remainder theorem.... will it work?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,317
    Thanks
    697
    well, n,2n and 3n are not pair-wise co-prime, so the chinese remainder theorem doesn't apply.

    however, if x = a (mod n), then x = a + kn. so x = 2a (mod 2n) is a + kn = 2a (mod 2n),

    that is kn = a (mod 2n). but it's hard to say more without knowing what a and n are (specifically, what gcd(a,n) might be).
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Member
    Joined
    Mar 2009
    Posts
    182
    Thanks
    1
    could we then not say that kn = 2nr + a

    so, k=2r +a/n

    then put it back into equation, so x = n(2r +a/n) + a

    x=2nr +2a

    2nr+2a = 3a(mod3n)

    2nr = a(mod3n)

    2nr = 3nu + a

    r = 3nu/2n + a/2n

    r = 3u/2 + a/2n

    x = 2n(3/2u + a/2n) + 2a

    x = 3nu + a +2a

    x = 3a + 3nu

    so x = 3a?

    Does that follow or have i broken some sort of modular rule along the way?

    Thanks
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,317
    Thanks
    697
    no, because 2r + a/n may not be an integer.

    suppose a = 2, and n = 3.

    x = 2 mod 3
    x = 4 mod 6 has no solution. if it did, we would have 3k+2 = 4 mod 6 for some integer k, hence 3k = 2 mod 6.

    but every integer of the form 3k is congruent to 3 or 0 mod 6.

    if you try to write 3k = 6r + 2, you get the solution k = r + 2/3, and sure, for r = 0, 3(2/3) is a multiple of 6.

    but 2/3 is not an integer. if we allowed non-integer solutions, we would get odd things like 1 = 3 (mod 3), since 1 = 3(1/3).

    as i said before, without knowing more about "a" and "n" there's not a more general statement about how to continue. there are values for a and n for which no solutions exist.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Arithmetic Progression or Arithmetic Series Problem
    Posted in the Math Topics Forum
    Replies: 1
    Last Post: October 8th 2009, 12:36 AM
  2. Short maths problem
    Posted in the Algebra Forum
    Replies: 3
    Last Post: August 12th 2009, 02:05 AM
  3. Replies: 3
    Last Post: June 1st 2008, 03:50 PM
  4. Help with one short problem.
    Posted in the Advanced Statistics Forum
    Replies: 3
    Last Post: February 18th 2007, 09:37 PM
  5. A short problem, help me please!
    Posted in the Algebra Forum
    Replies: 4
    Last Post: September 5th 2006, 02:13 PM

Search Tags


/mathhelpforum @mathhelpforum