Greatest Common Divisor(GCD) gcd(12,15)=3 gcd(12, 25 )=1, relative prime Theorem: ax= b mod m has a unique solution for every number b in Zm iff gcd(a, m)=IGreatest Common Divisor (GCD) • gcd(12,15) = 3 • gcd(12,25) = 1, relative prime • Theorem: ax = b mod m has a unique solution for every number b in Zm iff gcd(a,m) = 1