Is it true that if a divides bc, then there exist prime factors of a that divide both b and c

104 Views Asked by At

As per title really.

Is there a theorem (or similar) that states that given three positive integers a, b, c, if a | bc, then there exist prime factors p1, p2 of a such that p1 | b and p2 | c?

The specific case where I've come across this is Shor's algorithm, where a divides (x + 1)(x - 1).

1

There are 1 best solutions below

2
On BEST ANSWER

No.

If $a=15$ and $b=165$ and $c=91$ then $a \mid bc$ since $\frac{165\times 91}{15}=1001$ but there is no prime factor $p_2$ of $a$ such that $p_2 \mid c$

It becomes true if the highest common factors (greatest common divisors if you prefer) of $a$ and $b$ and of $a$ and $c$ are both greater than $1$. Here $p_1$ and $p_2$ may be the same prime factor of $a$, for example if $a$ is prime.