Theorem
A prime that divides a product, but not one factor, must divide the other factor
Quantitative Aptitude • Number System
Statement
Let be a prime number. If divides and does not divide , then divides .
How to use it
- 1Break the known factor into primes. If the prime you need is not among them, that prime must sit inside the other factor.
- 2Use it to turn 'divisible by 7' about a big expression into a small condition on one unknown.
Worked example
is divisible by 3, and is a digit from 1 to 9. Which values can take?
Step-by-step
- 1, so 3 is not a factor of 10.
Why: Check whether the known factor already supplies the prime.
- 2So 3 must divide :
. Why: The 3 has to come from somewhere, and 10 has none to give.
Answer
Watch out
It works for a prime only. 6 divides , yet 6 divides neither 4 nor 3.
Also known as
prime divides a product, Euclid's lemma, no common factor, 7 does not divide 99