Maths Olympiad Prep

Library / /93 of 462

Number theory Difficulty 5.1 AIME, harder Prove it Ireland

Find the smallest positive integer mm such that 5m5m is an exact 5th power, 6m6m is an exact 6th power, and 7m7m is an exact 7th power.

Solution

Let m=2a3b5c7dm = 2^a \cdot 3^b \cdot 5^c \cdot 7^d. NN where NN is a product of primes different from 22, 33, 55 and 77. For a number nn to be an exact 5th power, all the exponents in the prime factorisation of nn must be divisible by 55. Similarly for 6th and 7th powers.
For primes other than 22, 33, 55 and 77 the exponent in the prime decomposition of mm must be 00 or a multiple of 5×6×7=2105 \times 6 \times 7 = 210. The smallest solution will occur when each exponent is 00. Thus we can consider only numbers of the form 2a3b5c7d2^a \cdot 3^b \cdot 5^c \cdot 7^d.
For the conditions to be satisfied we must have 5c+15 \mid c+1, 6c6 \mid c and 7c7 \mid c. The smallest solution of this is c=84c = 84. To obtain aa we need to solve
a0(mod5)a+10(mod6)a0(mod7). a \equiv 0 \pmod{5} \quad a+1 \equiv 0 \pmod{6} \quad a \equiv 0 \pmod{7}.
The smallest solution is 3535. As bb satisfies the same equations, the smallest value of bb is also 3535. Finally, dd has to satisfy
d0(mod5)d0(mod6)d+10(mod7). d \equiv 0 \pmod{5} \quad d \equiv 0 \pmod{6} \quad d+1 \equiv 0 \pmod{7}.
The smallest solution is d=90d = 90. Putting everything together, the smallest value of mm is 5846357905^{84} \cdot 6^{35} \cdot 7^{90}.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.