• Support PF! Buy your school textbooks, materials and every day products Here!

Proof of zero divisor

  • Thread starter pivoxa15
  • Start date
  • #1
2,255
1

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.
 

Answers and Replies

  • #2
matt grime
Science Advisor
Homework Helper
9,395
3
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.
 
Last edited:
  • #3
2,255
1
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?
 
  • #4
matt grime
Science Advisor
Homework Helper
9,395
3
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.
 
Last edited:
  • #5
2,255
1
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?
 
Last edited:

Related Threads on Proof of zero divisor

  • Last Post
Replies
1
Views
912
  • Last Post
Replies
3
Views
5K
  • Last Post
Replies
1
Views
2K
  • Last Post
Replies
11
Views
4K
  • Last Post
Replies
13
Views
426
  • Last Post
Replies
7
Views
6K
  • Last Post
Replies
1
Views
3K
Replies
3
Views
931
  • Last Post
Replies
2
Views
3K
Replies
8
Views
2K
Top