Divisor of Product may not be Divisor of Factors
Jump to navigation
Jump to search
Theorem
Let $a, b, c \in \Z_{>0}$ be (strictly) positive integers.
Let:
- $c \divides a b$
where $\divides$ expresses the relation of divisibility.
Then it is not necessarily the case that either $c \divides a$ or $c \divides b$.
Proof
Let $c = 6, a = 3, b = 4$.
Then $6 \times 2 = 12$ so $c \divides a b$.
But neither $6 \divides 4$ nor $6 \divides 3$.
$\blacksquare$
Sources
- 1982: Martin Davis: Computability and Unsolvability (2nd ed.) ... (previous) ... (next): Appendix $1$: Some Results from the Elementary Theory of Numbers