Help With Proving a is Zero Divisor Mod n iff gcd(a,n)>1

[SomeRandomGuy]

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.

 

[SomeRandomGuy]

nevermind, I believe I solved it

 

[husseinshimal]

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