# if $b$ divides $ck$ and $b$ and $c$ are relatively prime, then $b$ must divides $k$

Suppose $b, c\in\mathbb{Z}$ and the greatest common divisor of $b$ and $c$ is $1$, i.e., $b$ and $c$ are relatively prime. If $b$ divides $ck$ for some positive integer $k$, then $b$ must divide $k$.

Could someone please give a proof for why $b$ must divide $k$?

This result is Gauß's lemma. It generalizes Euclid's lemma...

• Thank you SO MUCH. – gladimetcampbells Aug 3 '18 at 0:26

Here is a proof by contradiction:

If $b$ does not divide $k$, then $b$ and $k$ are also relatively prime. In this case $b$ and $ck$ must be relatively prime, since they share no prime factors (you could see this by, for example, using the fundamental theorem of arithmetic). But now $b$ does not divide $ck$.

• thank you so much. – gladimetcampbells Aug 3 '18 at 0:28
• "If b does not divide k, then b and k are also relatively prime." Uh, no they aren't. $6\not\mid 9$ but $6, 9$ are not relatively prime. – fleablood Aug 3 '18 at 1:06

Observe that the prime factorization of $ck$ is the product of the prime factorizations of $c$ and $k$. Since $b$ divides $ck$, all of $b$'s prime factors must appear somewhere in the prime factorization of $ck$ with the same multiplicity or greater. None of those factors are contributed by $c$, so they all must come from $k$. It follows that $b$ divides $k$. It's not totally rigorous but you can fill in the details.

• thank you so much. – gladimetcampbells Aug 3 '18 at 0:28

Well, let's think it out.

$b|ck$ so all the factors that make up $b$ divide into and are factors of $ck$. But none of the factors that make up $b$ can have anything to do with $c$. That means all the factors of $b$ are factors of just $k$. So $b|k$.

Can we formalize it?

Well, $b$ has a unique prime factorization. $b = \prod p_i^{k_i}$ for some unique set of primes $p_i$ and integer powers $k_i$. Meanwhile $ck$ also has a unique set of primes and powers and since $b|ck$ then each $p_i^{k_i}|ck$. However as none of the $p_i|c$ (because $b, c$ are relatively prime) it must be by Euclide's Lemma that $p_i|k$ and that as $p_i^{k_i}|b$ and $b|ck$ then $p_i^{k_i}|k$. That holds true for each of the $p_i, k_i$ values so as it holds true for all of them it holds true for $b = \prod p_i^{k_i}$.

=====

This might be a little ham fisted.

Let $b = \prod p_i^{m_i}$ be the prime factorization of $b$.

Let $c = \prod q_j^{v_j}$ be the prime factorization of $c$. As $b$ and $c$ are relatively prime none of the $p_i$ are equal to any of the $q_i$.

Let $k = \prod p_{n_i}^{j_{n_i}} \times \prod r_w^{v_w}$ be the prime factorization of $k$ where $p_{n_i}$ are some of the prime $p_i$ that factor $b$ and $r_i$ are primes that do not factor $b$.

So $\frac {kc}{b} = \frac {\prod q_j^{v_j}\times \prod p_{n_i}^{j_{n_i}} \times \prod r_w^{v_w}}{\prod p_i^{m_i}}$ is an integer.

Now that means all the $p_i^{m_i}$ in the denominator must be accounted for in the primes in the numerator but none of those primes can be any of $q_i$ or the $r_w$ so must be that they are accounted for entirely by the $\prod p_{n_i}^{j_{n_i}}$.

So $b|\prod p_{n_i}^{j_{n_i}}$ and $\prod p_{n_i}^{j_{n_i}}|k$ so $b|k$.
{"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": 1, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0, "math_score": 0.9363601207733154, "perplexity": 88.78308753474609}, "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": "plain"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "warc_path": "s3://commoncrawl/crawl-data/CC-MAIN-2021-17/segments/1618038917413.71/warc/CC-MAIN-20210419204416-20210419234416-00226.warc.gz"}