2020 AIME I Problems/Problem 10
Let and be positive integers satisfying the conditions
is a multiple of and
is not a multiple of
Find the least possible value of
Taking inspiration from we are inspired to take to be , the lowest prime not dividing , or . Now, there are factors of , so , and then for . Now, . Noting is the minimal that satisfies this, we get . Thus, it is easy to verify this is minimal and we get . ~awang11
Assume for the sake of contradiction that is a multiple of a single digit prime number, then must also be a multiple of that single digit prime number to accommodate for . However that means that is divisible by that single digit prime number, which violates , so contradiction.
is also not 1 because then would be a multiple of it.
Thus, is a multiple of 11 and/or 13 and/or 17 and/or...
Assume for the sake of contradiction that has at most 1 power of 11, at most 1 power of 13...and so on... Then, for to be satisfied, must contain at least the same prime factors that has. This tells us that for the primes where has one power of, also has at least one power, and since this holds true for all the primes of , . Contradiction.
Thus needs more than one power of some prime. The obvious smallest possible value of now is . Since , we need to be a multiple of 11 at least that is not divisible by and most importantly, . is divisible by , out. is divisible by 2, out. is divisible by 5, out. is divisible by 2, out. and satisfies all the conditions in the given problem, and the next case will give us at least , so we get .
Solution 3 (Official MAA)
Let and be positive integers where is a multiple of and is not a multiple of . If a prime divides , then divides , so it also divides , and thus divides . Therefore any prime dividing also divides both and . Because is relatively prime to , the primes , , , and cannot divide . Furthermore, because is divisible by every prime factor of , but is not a multiple of , the integer must be divisible by the square of some prime, and that prime must be at least . Thus must be at least .
If , then must be a multiple of but not a multiple of , and must be divisible by . Therefore must be a multiple of that is greater than . Let , with . Then . The least for which is not divisible by any of the primes , , , or is , giving the prime . Hence the least possible when is .
It remains to consider other possible values for . If , then must be divisible by but not , and must be a multiple of , so . Then . All other possible values for have , and in this case , so . Hence no greater values of can produce lesser values for , and the least possible is indeed .
|2020 AIME I (Problems • Answer Key • Resources)|
|1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15|
|All AIME Problems and Solutions|