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

-

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

## 1 Answer

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

-
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

1
@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

1
@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
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 16, "mathjax_display_tex": 1, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9539130926132202, "perplexity_flag": "middle"}