- #1

SomeRandomGuy

- 55

- 0

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.