# A congruence problem

Prove that if $\gcd(a,b)=d$ and $d$ divides $f$, then there is a an integer $k$ such that $a\cdot k \equiv f\pmod b$.

-
you haven't said what k is. –  user16697 Nov 11 '11 at 4:49

If $\gcd(a,b)=d$, then you can find integers $r$ and $s$ such that $ar+bs=d$. Since $d$ divides $f$, there exists $t$ such that $dt=f$. Therefore, $$f = dt = (ar+bs)t = a(rt) + b(st) \equiv a(rt)\pmod{b}.$$ So setting $k=rt$ shows there exists a $k$ with $ak\equiv f\pmod{b}$.