Proving Addition & Multiplication in Zn Are Well-Defined

[UofC]

Homework Statement

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

Homework Equations

The Attempt at a Solution

I have no idea where to start.

 

[matt grime]

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?

 

[HallsofIvy]

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?

 

[UofC]

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.