Why does Euclid's lemma have the requirement of coprimes?

Question

I was reading the general form of Euclid's lemma which states:

If $a \mid bc$ and $a$ is relatively prime to $b$ then $a \mid c $

I don't really understand why the "relative prime" condition is there.
If for instance we take as $a = 49$ and $b = 91$ then $\gcd(a,b) = 7$
So then we would have:
$ax + by = 7 \Leftrightarrow cax + cby = 7c$
We know that $a \mid cax$
We also know that $a \mid bc \Rightarrow a \mid cby$
So $a \mid 7c$
But we already know that $a \nmid 7$ because $\gcd(a, b) = 7$ so $a\mid c$

So it seems to me that we can prove the lemma without specifying prime relativity.

What am I doing wrong here?

Answer 1

Yes, you need coprime.

Theorem. Let $a$ and $b$ be integers such that $a\nmid b$. If $\gcd(a,b)\gt 1$, then there exists $c$ such that $a\mid bc$ but $a\nmid c$.

Proof. Let $d=\gcd(a,b)$; then we can write $a=da'$ and $b=db'$, with $\gcd(a',b')=1$. Let $c=a'$. Then $ba'= db'a' = da'b' = ab'$, so $a|bc$. However, $a$ does not divide $a'$, since $a'\lt a$ (because $d\gt 1$). $\Box$

So absolutely nothing short of "$a$ and $b$ coprime" will allow you to go from $a|bc$ to $a|c$. If $a$ and $b$ are not coprime, then there always exist values of $c$ that make the antecedent true (that is, $a|bc$), but the consequence false (that is, $a\nmid c$).

As to what you present: First, that $7$ is a linear combination of $a$ and $b$ does not, by itself, mean $\gcd(a,b)=7$; it means $\gcd(a,b)$ divides $7$. And you cannot go from $a|7c$ and $a\nmid 7$ to $a|c$; that is, after all, what you claim to be trying to prove, and you cannot when $\gcd(a,7)\neq 1$ (see above).

What you have correctly established the following:

If $a|bc$, then $a|\gcd(a,b)c$.

You may think of that as a generalization of Euclid's lemma (since it yields Euclid's Lemma when $\gcd(a,b)=1$); but you cannot go from that to deduce $a|c$.

As to proving that statement, what you have works: let $d=\gcd(a,b)$. There exist $x,y\in\mathbb{Z}$ such that $ax+by=d$, hence $axc+bcy=dc$. Since $a|axc$ and $a|bcy$, then $a|dc=\gcd(a,b)c$, as desired.

But that's where you get stopped. You cannot go further if $\gcd(a,b)\neq 1$.

Answer 2

The mistake you're making is that you chose an $a$ to be the greatest common denominator of the numbers. The requirement that they be relatively prime is easier to see if you look at the prime decomposition of the numbers involved. Say $bc= p_1p_2p_3$ for $p_k$ distinct primes and take $a=p_1$. Now if $b=p_1p_2$ it is not relatively prime to $a$ anymore but we're forced to have $c=p_3$ and since the primes are distinct $a_1$ cannot divide $p_3$.

If instead we take $b=p_2p_3$ then $a$ is relatively prime to $b$ and in this case $c=p_1$ and indeed $a$ divides $c$ in this case, since we're assured they have a prime in common. The relatively prime requirement ensures that the primes are distributed correctly between $b$ and $c$ in the product $bc$ to ensure $a$ divides $c$.

Answer 3

$$a\nmid 7\implies a\neq 7\implies \gcd(a,b)\neq \gcd(7,b)=7$$ So you can't implies it doesn't divide into the gcd, ( which can actually be 1 or 7 in the $\gcd(7,b)$ ). The main point is, if it's not coprime it can take the factor it has in common from $b$ , and the ones it doesn't have in common from $c$ . If the gcd is 1 however, then it takes all factors from $c$ necessarily.

Answer 4

$$ 6\mid 4\times3 \text{ but } 6\nmid4 \text{ and }6\nmid 3. $$ It one drops the requirement of coprimality, then $6\mid4\times3$ would imply that $6\mid4$ or $6\mid3.$