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$.
Tell me more
×
Mathematics Stack Exchange is a question and answer site for
people studying math at any level and professionals in related fields. It's 100% free, no registration required.
|
|
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}$. |
|||||||||||
|
