# Are there integers $a,b,c$ such that $a$ divides $bc$, but $a$ does not divide $b$ and $a$ does not divide $c$?

Are there integers $a,b,c$ such that $a$ divides $bc$, but $a$ does not divide $b$ and $a$ does not divide $c$?

I am not quite sure what to do with the given information. I know I could easily find an example.

We know that $a$ divides $bc$ so,

$$bc=aq \text{ for some integer } q.$$

And that $a$ does not divide $b$ or $c$ so, how is that represented?

What would be my first step?

• oodles. Just need a=mn to be composite. Then $a|mn$ but not $a|m$ nor $a|n$. Or more generally if you "split the factors" of a between b and c. a = mn and b= mk where n not |k and b = nj where m not |j. will do it. a = 8 then b=2*7 and c =4*29 will do it. If a = 12 then b=3*anything not divisible by 4 and c = 4*anything not div by 3. or b =2*anything not div by 6 and c=6* anything odd. etc. – fleablood Sep 5 '16 at 20:05

$$4~|~2\times2$$ $$\quad\quad\quad$$

$6$ divides $3\times 8$, but $6$ does not divide $3$ and $6$ does not divide $8$.

If a prime number divides the product of two numbers, then it divides one of those two numbers. That's "Euclid's lemma". (So $6$ is not prime.)

The general result on this question is this generalisation of Euclid's lemma:

Gauß's lemma: If a number divides a product of two factors, a,d is coprime with one of them, it divides the other.

oodles.

We just need $a=mn$ to be composite. ($m > 1; n> 1$ all variables are assumed to be integers.)

The we can "split the factors" by letting $b = m\cdot \text{(anything not divisible by$n$)}=mk$ and $c = n\cdot \text{(anything not divisible by$m$)}=nj$.

Then $\frac ba = \frac {mk}{mn} = \frac kn \not \in \mathbb Z$ and $\frac ca= \frac {mj}{mn} = \frac jm \not \in \mathbb Z$. But $\frac {bc}{a} = \frac {mnjk}{mn} = jk \in \mathbb Z$.

If $a$ is prime though this will not be possible. That should be clear right?

If $b = \prod p_i^{m_i}$ and $c = \prod q_i^{n_i}$ where $p_i, q_i$ are prime and $a$, a prime, divides $bc = \prod p_i^{m_i}\prod q_i^{n_i}$ then $a$ must equal one of the $p_i$ or $q_i$ and must therefore divide either $a$ or $b$.

If $a$ is composite, this can be avoided by either $pq\mid a$ with $p\mid b$ and $q\mid c$ but not vice versa, or by $p^m\mid a$ and $p\mid a$ and $p\mid b$ but not to the full power of $m$.

====

"$bc=aq$ for some integer $q$; what should be my next step?"

$$bc = \frac a{\gcd(a,b)}\gcd(a,b)q ; \text{ let } q = \frac{b}{\gcd(a,b)}\cdot k.$$

$$bc = \frac a{\gcd(a,b)}bk$$

$c = \frac a{\gcd(a,b)}k$; let $k$ be anything that isn't a multiple of $\gcd(b,a)$.

This requires $\gcd(b,a) \ne 1$ and $a\not \mid b$.

Example: $a = 36$, $b = 48$: $a = 3\cdot 12; b = 4\cdot 12$ so $c = 3\cdot k; 12\not \mid k$, say $k = 7;c =21$.

So $36\mid 21\cdot 48= 7\cdot 36\cdot 4$ but $36\nmid 21$ and $36\nmid 48$.