Take the 2-minute tour ×
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.

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$.

share|improve this question
you haven't said what k is. –  user16697 Nov 11 '11 at 4:49

1 Answer 1

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}$.

share|improve this answer
it has to get like at-f==(mod b), from the new variable from f=dt eqn and –  Jeffry Nov 11 '11 at 5:30
@Jeffry: I have no idea what that means. If you have specific requirements in the problem, then I can't know them unless you tell us. The government doesn't let me read minds without a warrant. –  Arturo Magidin Nov 11 '11 at 5:31
@Jeffry: "It has to get like"; What has to get like what? What "new variable". I'm sorry, but that sentence just doesn't parse. I don't understand what you are trying to say, or what the problem is. –  Arturo Magidin Nov 11 '11 at 5:59

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.