2018 AMC 10A Problems/Problem 22
Let and be positive integers such that , , , and . Which of the following must be a divisor of ?
The GCD information tells us that divides , both and divide , both and divide , and divides . Note that we have the prime factorizations:
Hence we have for some positive integers . Now if divides , then would be at least which is too large, hence does not divide . Similarly, if divides , then would be at least which is too large, so does not divide . Therefore, where neither nor divide . In other words, is divisible only by primes that are at least . The only possible value of between and and which fits this criterion is , so the answer is .
We can say that and 'have' , that and have , and that and have . Combining and yields has (at a minimum) , and thus has (and no more powers of because otherwise would be different). In addition, has , and thus has (similar to , we see that cannot have any other powers of ). We now assume the simplest scenario, where and . According to this base case, we have . We want an extra factor between the two such that this number is between and , and this new factor cannot be divisible by or . Checking through, we see that is the only one that works. Therefore the answer is
Solution by JohnHankock
Solution 3 (Better notation)
First off, note that , , and are all of the form . The prime factorizations are , and , respectively. Now, let and be the number of times and go into , respectively. Define , , , and similarly. Now, translate the s into the following:
From , we see that , thus from , . Similarly, from , , thus from , .
Note also that and . Therefore Thus, for some having no factors of or .
Since , the only values for k are , but all have either factors of or , except . And we're done.
~Rowechen Zhong ~MannsNotHot
Solution 4 (Fastest)
Notice that , so must be a multiple of . The only answer choice that gives a value between and when multiplied by is . - mathleticguyyy + einstein
In the case where there can be 2 possible answers, we can do casework on ~Williamgolly
Since , and for some positive integers such that and are relatively prime.
Similarly , since , we have and with the same criteria. However, since is not a multiple of , we must contribute an extra to in order to make it a multiple of . So, is a multiple of three, and it is relatively prime to .
Finally, , so using the same logic, is a multiple of and is relatively prime to where .
Since we can't really do anything with these messy expressions, we should try some sample cases of and . Specifically, we let or , and see which one works.
First we let . Note that all of these values of work for the first expression because they are all not divisible by .
Without the loss of generality, we let for all of our sample cases. We can also adjust the value of in , since there is no fixed value for ; there is only a bound.
So we try to make our bound satisfactory. We do so by letting .
Testing our first case and , we find that . To simplify our work, we note that , so for all is equal to .
So now, we can easily find our values of :
We can clearly see that only is in the bound . So, must be a divisor of , which is answer choice .
The relationship of , , , and is shown in the above diagram. . , ,
Note that is not required to solve the problem.
Solution 7 (Easier version of Solution 1)
Just as in solution , we prime factorize and to observe that
Substituting these expressions for and into the final given,
The greatest common divisor of these two numbers is already . If is what we wish to multiply by to obtain the gcd of these two numbers, then
. Testing the answer choices, only works for (in order for the compound inequality to hold). so our gcd is , which means that must divide .
-Benedict T (countmath1)
Video Solution by Richard Rusczyk
Video Solution by OmegaLearn (Meta-Solving Technique)
|2018 AMC 10A (Problems • Answer Key • Resources)|
|1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 • 16 • 17 • 18 • 19 • 20 • 21 • 22 • 23 • 24 • 25|
|All AMC 10 Problems and Solutions|