1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
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: Proof of zero divisor

  1. Mar 11, 2007 #1
    1. The problem statement, all variables and given/known data
    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.

    3. 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.
  2. jcsd
  3. Mar 11, 2007 #2

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    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: Mar 11, 2007
  4. Mar 11, 2007 #3
    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


    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?
  5. Mar 12, 2007 #4

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    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: Mar 12, 2007
  6. Mar 12, 2007 #5
    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


    Rigorous enough?
    Last edited: Mar 12, 2007
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook