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

Help with a proof

  1. Feb 17, 2008 #1
    Prove that a number a is a zero divisor mod n iff gcd(a,n)>1.

    I have the proof assuming a is a zero divisor mod in => gcd(a,n)>1. However, going in the other direction has me stumped. Basically, here is all I have so far that I feel is correct:

    Assume gcd(a,n)=d>1
    => da' = a and dn' = n and if x|a and x|n => x|d
    Thus, there exists w,z where aw + nz = d
    => aw = d mod n.

    I've tried subbing in from here. in a few different ways but I feel like it just leads me into a brick wall. Ultimately, i'm looking to get aw = 0 mod n which makes a a zero divisor.
  2. jcsd
  3. Feb 17, 2008 #2
    nevermind, I believe I solved it
  4. Feb 19, 2008 #3
    I hope this would be helpful

    ok,i asked some mathematicians and they replied with this:Think about n/gcd(a,n) - let's call this b. First of all, you can be sure that b is an integer - why ? Secondly, you can be sure that if gcd(a,n) > 1 then b mod(n) is not 0 - why ? Now think about the product ab - what is ab mod(n) ? How does this help you show that a is a zero divisor mod(n) ?p.s:you can finde more help on http://en.wikipedia.org/wiki/Wikipedia:Reference_desk/Mathematics
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook