note: (a,m)=gcd(a,m) Theorem: ax≡ay (mod m) if and only if x≡y (mod m/(a,m)) And then in the middle of a certain proof later on, my textbook says: Suppose (a,m)|b. Then BY THE ABOVE THEOREM(?), ax≡b (mod m) if and only if (a/(a,m))x ≡ b/(a,m) (mod m/(a,m))? But I don't see exactly why the above theorem will give us this result. First of all, I don't think on the RHS, b is necessarily a multiple of a. Secondly, the theorem says we can divide the LHS and RHS by a (not (a,m)), and divide the modulus by (a,m), NOT a. But in that proof, they divide everything by (a,m) which is not what the theorem says. Could someone please show me how to apply the theorem in a way that will lead us to this result? I really don't see how... Is it also true that ax≡ay (mod m) if and only if (a/(a,m))x ≡ (a/(a,m))y (mod m/(a,m))? I'm confused... I hope someone can explain this. Any help is much appreciated!