Results 1 to 8 of 8

Math Help - Trouble learning how to manipulate congruences

  1. #1
    Newbie
    Joined
    Jun 2010
    Posts
    6

    Trouble learning how to manipulate congruences

    I am having some trouble learning how to manipulate congruences, and have two questions on things I don't understand:

    1. I understand that the following:

    a +_n (b +_n c) \equiv a + (b +_n c) \pmod{n}

    comes directly from the definition of the rule for +_n
    But why is the following also true?:

    a + (b +_n c) \equiv a + (b + c) \pmod{n}

    2. Why is the following true?

    3^{18*3+1} \equiv (3^{18})^3 * 3 \pmod{19}

    Thanks,
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Newbie
    Joined
    Jun 2010
    Posts
    6
    OK, I've just realised (2) has nothing to do with congruences and just comes from manipulation of powers. I still don't get (1).
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member Bacterius's Avatar
    Joined
    Nov 2009
    From
    Wellington
    Posts
    927
    a + (b +_n c) \equiv a + (b + c) \pmod{n}

    Remember this is just addition so you don't need those brackets :

    a + b +_n c \equiv a + b + c \pmod{n}

    By simplifying :

    _n c \equiv c \pmod{n}

    Which must be true.

    ~~~~

    Basically, in a congruence you can do about everything except using logarithms, you need care when working with square roots, and to divide you must multiply by the inverse modulo n. Here are the formulae :

    a \equiv b \pmod{n} \ \implies \ a + c \equiv b + c \pmod{n}

    a \equiv b \pmod{n} \ \implies \ a \times c \equiv b \times c \pmod{n}

    a \equiv b \pmod{n} \ \implies \ a^c \equiv b^c \pmod{n}

    \frac{a}{b} \equiv a \times b^{-1} \pmod{n} if and only if \gcd{(b, n)} = 1.

    This is about everything to begin. You'll see that we can also simplify powers using various powerful tools.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Newbie
    Joined
    Jun 2010
    Posts
    6
    I should have said this originally, but the result I am having trouble with comes from a proof in a textbook of why +_n is associative, so I can't just remove the brackets on the basis of +_n being associative.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Super Member Bacterius's Avatar
    Joined
    Nov 2009
    From
    Wellington
    Posts
    927
    Ah, I see. Are you allowed to substract a from both sides ?
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Newbie
    Joined
    Jun 2010
    Posts
    6
    Yes, you can subtract a congruent number from both sides, or add a congruent number to both sides, or multiply both sides by a congruent number, or raise both sides to a power.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Super Member Bacterius's Avatar
    Joined
    Nov 2009
    From
    Wellington
    Posts
    927
    Well then you could just substract a from both sides, and then the brackets could be removed because they would be clearly useless regardless of whether you proved the associativity theorem. What do you think ?
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Newbie
    Joined
    Jun 2010
    Posts
    6
    Thanks! I knew it had to be something staring me in the face!
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 13
    Last Post: June 1st 2010, 04:52 PM
  2. Trouble solving a system of linear congruences.
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: April 14th 2010, 11:10 AM
  3. Matlab structure manipulate?
    Posted in the Math Software Forum
    Replies: 0
    Last Post: April 12th 2010, 07:30 AM
  4. Manipulate big equation
    Posted in the Algebra Forum
    Replies: 11
    Last Post: March 2nd 2010, 03:14 AM
  5. Manipulate Math with Java
    Posted in the Math Forum
    Replies: 0
    Last Post: September 27th 2009, 12:24 PM

Search Tags


/mathhelpforum @mathhelpforum