Results 1 to 5 of 5

Math Help - Reducing the modulo

  1. #1
    Forum Admin topsquark's Avatar
    Joined
    Jan 2006
    From
    Wellsville, NY
    Posts
    9,845
    Thanks
    320
    Awards
    1

    Reducing the modulo

    Sorry about the title, I can't remember how this works and after an hour on the internet I still have no clue what to call it. I would like to check my method on the following equations.

    Solve 6x \equiv 3~\text{(mod 9)}

    Since gcd(6, 9) = 3 \neq 1 we can divide through and get
    2x \equiv 1~\text{(mod 3)}

    This is the line I am not sure of, but it does give a correct answer (x = 2) for the original equation.

    again,
    Solve 6x \equiv 3~\text{(mod 7)}

    Now in this case gcd(6, 7) = 1, so we can't "reduce" the mod by dividing.

    How far off base am I? I could swear I've seen some way to reduce the mod to make the equation simpler, but I cannot for the life of me remember what the circumstances were.

    -Dan
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member PaulRS's Avatar
    Joined
    Oct 2007
    Posts
    571
    Quote Originally Posted by topsquark View Post
    Solve 6x \equiv 3~\text{(mod 9)}

    Since gcd(6, 9) = 3 \neq 1 we can divide through and get
    2x \equiv 1~\text{(mod 3)}
    By definition: 6x \equiv 3 (\bmod.9) if and only if 9 divides (6x-3) = 3\cdot ( 2x - 1), and this happens if and only if 3 divides 2x-1 -since we need another factor of 3- i.e. 2x\equiv 1 (\bmod.3) indeed.

    (note then that it is true that if both sides have a common factor that divides the module we can divide everything - both sides and the module - by that number )

    Quote Originally Posted by topsquark View Post

    Solve 6x \equiv 3~\text{(mod 7)}

    Now in this case gcd(6, 7) = 1, so we can't "reduce" the mod by dividing.
    Yes, but in this case since \text{gcd}(6, 7) = 1 it follows that 6 has a multiplicative inverse module 7 .
    In fact 6\equiv -1 (\bmod.7) so you have -x\equiv 3 (\bmod.7) ...

    More generally, if you wanted to find the modular inverse here are a couple of ways:
    1. Use the extended euclidean algorithm -this works always.
    2. If the module were a prime p, note that by Fermat's Little Theorem, since a^{p-1}\equiv 1 (\bmod. p) then a and a^{p-2} are modular inverses, and so you compute a^{p-2}(\bmod.p) by repeatedly squaring and taking modules at each step.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Forum Admin topsquark's Avatar
    Joined
    Jan 2006
    From
    Wellsville, NY
    Posts
    9,845
    Thanks
    320
    Awards
    1
    So if I understand this:

    Solve 4x \equiv 6 ~\text{(mod 10)}

    We have gcd(4, 10) = 2. Thus we know that if 4x - 6 = 2(2x - 3) is divisible by 10 then 2x - 3 is divisible by 5.

    Thus we can solve 2x \equiv 3 ~\text{(mod 5)}

    which has x = 4 as its only solution (mod 5), thus x = 4 is the only solution (mod 10) to the original problem as well. (check!)

    -Dan
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member PaulRS's Avatar
    Joined
    Oct 2007
    Posts
    571
    Almost correct , x \equiv 4 (\bmod.5) means that either x\equiv 4 (\bmod.10) or x\equiv 9 (\bmod.10)

    Note that you have a degree of freedom in what x is in module 2 . This happnes because fixing the values of x(\bmod. b_1) and x (\bmod.b_2) determines uniquely x (\bmod.b_1\cdot b_2) and viceversa, when (b_1,b_2)=1. (this is a particular case of the Chinese Remainder Theorem )
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Forum Admin topsquark's Avatar
    Joined
    Jan 2006
    From
    Wellsville, NY
    Posts
    9,845
    Thanks
    320
    Awards
    1
    Quote Originally Posted by PaulRS View Post
    Almost correct , x \equiv 4 (\bmod.5) means that either x\equiv 4 (\bmod.10) or x\equiv 9 (\bmod.10)

    Note that you have a degree of freedom in what x is in module 2 . This happnes because fixing the values of x(\bmod. b_1) and x (\bmod.b_2) determines uniquely x (\bmod.b_1\cdot b_2) and viceversa, when (b_1,b_2)=1. (this is a particular case of the Chinese Remainder Theorem )
    Thanks. That's actually explains something I had found. In mod 5 the only answer was x = 4. But in mod 10 I could construct a general solution x = 5n + 4 (mod 10) for integer n, but I couldn't find a way to do that in mod 5.

    -Dan
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Simplifying/Reducing
    Posted in the Algebra Forum
    Replies: 7
    Last Post: September 15th 2011, 02:03 PM
  2. Modulo of squares = modulo of roots
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: December 1st 2009, 09:04 AM
  3. Reducing the set
    Posted in the Advanced Algebra Forum
    Replies: 6
    Last Post: October 7th 2009, 11:02 AM
  4. Row Reducing with a Variable
    Posted in the Advanced Algebra Forum
    Replies: 2
    Last Post: July 22nd 2009, 09:27 PM
  5. Reducing Roots
    Posted in the Algebra Forum
    Replies: 5
    Last Post: June 6th 2009, 12:54 PM

/mathhelpforum @mathhelpforum