1
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ Thank you SO MUCH. $\endgroup$ – gladimetcampbells Aug 3 '18 at 0:26
1
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ thank you so much. $\endgroup$ – gladimetcampbells Aug 3 '18 at 0:28
  • 1
    $\begingroup$ "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. $\endgroup$ – fleablood Aug 3 '18 at 1:06
1
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ thank you so much. $\endgroup$ – gladimetcampbells Aug 3 '18 at 0:28
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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