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.