Prove that a number a is a zero divisor mod n iff gcd(a,n)>1.(adsbygoogle = window.adsbygoogle || []).push({});

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.

**Physics Forums | Science Articles, Homework Help, Discussion**

Join Physics Forums Today!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

# Help with a proof

**Physics Forums | Science Articles, Homework Help, Discussion**