1. Not finding help here? Sign up for a free 30min 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!

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
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?

Similar Discussions: Help with a proof
  1. Proof help (Replies: 4)

  2. Help with proof (Replies: 1)

  3. Help with a proof (Replies: 3)

  4. Help with a proof (Replies: 2)

  5. Help with a proof. (Replies: 5)