Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: I need help with proofs.

  1. Apr 22, 2007 #1
    1. The problem statement, all variables and given/known data

    So I have to prove that addition and multiplication in Zn are well defined.

    2. Relevant equations

    3. The attempt at a solution

    I have no idea where to start.
  2. jcsd
  3. Apr 23, 2007 #2

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    Ah, the old well defined is never well defined issue. Perhaps.

    What are the elements of Z_n? They are equivalence classes of integers such as [1], which means the set {1,n+1,2n+1,...}.

    How do we add class [a] and ? We write [a+b], and similarly [a]=[ab]. This means we pick an element of the class [a] and one of and add/multiply in the integers, and take the class of the result.

    The question asks you to show that the result doesn't depend on the choice of element we make. That is [1][2] should be the same as [n+1][-3n+2], or that 1*2=(n+1)*(-3n+2) mod n.

    Is that helpful for you?
  4. Apr 23, 2007 #3


    User Avatar
    Science Advisor

    Proving that addition and multiplication are "well defined" means proving that the sum and product of any two members of the set is a unique member of the set. How you do that depends strongly on how you are defining addition and multiplication!

    The standard definition of addition and multiplication of "equivalence classes" (which is what you are doing here: Two integers, x and y, are said to be equivalent if and only if x-y is divisible by n. That divides all integers into equivalence classes called Z_n.) is as matt grime said: To add (multiply) two such classes X and Y, select an integer from X and an integer from Y. Add (multiply) those integers. The resulting integer is in some equivalence class and that is defined as the sum X+Y (product XY).

    For example, suppose a is contained in X and b in Y. X+Y= Z where Z is the equivalence class containing a+b. Now suppose a' is also contained in X and b' also contained in Y. That is, a-a'= pn and b-b'= qn for integers q and n. Can you show that a'+ b' is also contained in Z? That is, that a'+ b' is equivalent to a+ b?
  5. Apr 23, 2007 #4
    After a lot of thinking and an allnighter, think I got it, allong with the rest of my problem set. Now I turn it in and :zzz:

    Thanks guys.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook