Problem:
Let and be positive integers satisfying the conditions
,
is a multiple of , and
is not a multiple of .
Find the least possible value of .
Solution:
Let and be positive integers such that is divisible by , but is not divisible by . Suppose a prime divides . Then divides , so must also divide . This implies that divides as well. Therefore, every prime divisor of also divides .
Now, consider . Since each prime dividing also divides , it must divide as well. Hence, all prime divisors of divide .
We are told that is relatively prime to . Therefore, none of the primes , , , or can divide .
Additionally, since all prime divisors of divide , but is not divisible by , it must be that includes repeated prime factors that are not fully present in —that is, is divisible by the square of at least one prime. This prime must be at least , as smaller primes are excluded.
Therefore, the smallest possible value of is .
Suppose . Then must be divisible by but not by , and must be divisible by . This means that must contain enough factors of so that has at least factors of . Since each factor of in contributes one factor per power of , we need .
Write , where . Then the value of . We are told that is relatively prime to , so must not be divisible by any of these primes.
The smallest integer such that is relatively prime to is , since , which is a prime greater than and not divisible by , , , or .
Therefore, the smallest possible value of when is
It remains to consider other possible values for . Suppose . Then must be divisible by but not by , and must be divisible by
so we must have . This implies
For any larger possible value of , we must have since must be divisible by the square of some prime . In such cases, , so
Thus, no greater value of can produce a smaller value of , and the smallest possible value of is
The problems on this page are the property of the MAA's American Mathematics Competitions