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