Proof of zero divisor

[pivoxa15]

Homework Statement

Prove that if A, a non zero element in Zn (integers mod n) is not a unit then A is a zero divisor in Zn.

The Attempt at a Solution

[AB] does not equal 1 mod n for some A and all B in Zn
=> the element A is a multiple of n so n divides A because otherwise there should be a remainder of 1.
=> AB=0 for all B in Zn

So A is a zero divisor in Zn.

I feel the first implication is a bit unrigorous.

 

[matt grime]

It is very unrigorous. You are flitting between Z/nZ, and Z at will and making no comment about what you're doing.

2 is a zero divisor mod 4. Are you claiming 2 is a multiple of 4 (in the integers)? There is also no reason why AB=0 for all B. Indeed this is clearly false if you let B=1 (since A is not zero). Notice that your other thread on zero divisors now contradicts the definition you need here. 0 is obviously not a unit, and by your previous thread, not a zero divisor either. In fact what you've just argued is that the only zero divisor is 0 (you just asserted in your first step that n divides A, i.e. A=0 mod n).

Something in Z is a unit when reduced mod n if and only if it is coprime to n. That is a starting hint.

 

[pivoxa15]

Note that A must be nonzero.

Your hint is useful. If we assume it and use it's negatation then

A in Z is not a unit when reduced mod n if and only if it is not coprime to n.

=> There exists b such that b|a and b|n. for b>1.
=> A=bi, n=bj, 1<j<n so j is an element in Z mod n
=> n|Aj
=> Aj mod n = 0
=> A is a 0 divisor in Z mod n

Correct?

If so then I like to prove the assumption we used which was also your hint. I seem to have some trouble doing this. Could yoy maybe give a hint of how to prove that?

 

[matt grime]

Assumption? That the units mod n are the residues coprime with n? This is the first thing you shuold have proved, and is a simple consequence of Euclid's algorithm. It involves coprimality. There isn't a great deal else you can do than invoke Euclid/highest common factor stuff.

 

[pivoxa15]

I will do the proof from the beginning

First prove
A in Zn is coprime to n
=> gcd(A,n)=1
=> Use theorem involving Eulid's algorithm that there is a B in Zn and k such that AB+kn=1
=>Ab is congruent to 1 mod n
=>A is a unit

So from the above lemma we can turn it around so that
A is not a unit
=> A is not coprime to n
=> gcd(A,n)=d>1
=> Suppose A=ad and n=bd
=> Ab-na=adb-bda=0 since multiplication is commutative
=> Ab=0 mod n for some non zero b in Zn
=> A is a zero divisor in Zn

QED

Rigorous enough?