# There are infinitely many $N$ such that $\frac{N}{2}$ is a perfect square, $\frac{N}{3}$ is a perfect cube, and $\frac{N}{5}$ is a perfect fifth power

Show that there are infinitely many $N$ such that $\frac{N}{2}$ is a perfect square, $\frac{N}{3}$ is a perfect cube, and $\frac{N}{5}$ is a perfect fifth power.

A hint is given with this question, which is: $7^{30}$ is a perfect square, a perfect cube and a perfect fifth power.

Can anyone solve this? Thanks!

• I wonder who used this in a contest. It appeared as an exercise in Albert Beiler's book popularizing Number Theory in 1962 or so. It might not have been new even then. – Gerry Myerson Jun 14 '13 at 9:37
• It is an exercise from a book called 'Basics of Math Olympiad', not from the contest itself, I think I have tagged the 'contest-math' wrongly. Anyway what's the name of the book from which this exercise came? – Dave Clifford Jun 14 '13 at 9:45
• The book where I saw it is Recreations in the Theory of Numbers: the Queen of Mathematics Entertains, and the first publication was 1964. – Gerry Myerson Jun 14 '13 at 10:07

The general form of this kind of number is $2^{15}3^{10}5^{6}x^{30}$, for all values of $x$.

When $x=1$, this number is the product of powers of 2, 3, and 5 just under some integer, eg $32768$, $59049$ and $15625$ are the largest powers under, say $60,000$.

The general working for such a number is to treat the indeces by chinese remainder. So, for example, should we seek something where $N/2$ is square, $N/3$ is cube, and $N/5$ is a fifth power, we would note that, eg it is a product of some powers of 2, 3, and 5, eg $2^a 3^b 5^c$.

We have then that 2 divides $a-1, b, c$, 3 divides each of $a, b-1, c$ and 5 divides each of $a, b, c-1$. We get then that 15 divides a, 10 divides b, and 6 divides c.

• We find now a multiple of 15 that 2 divides a-1: result = $a=15$
• We find then that 10 that 3 divides b-1, result $b = 10$
• We find a result where 5 divides c-1: result = $6$.

We then note that every number that is a power of 30, is already a square, a cube, and a fifth power, ie $x^{2 \cdot 3 \cdot 5} = x^{30}$, and thus if $N/2$ is square, so is $(N\cdot x^{30})/2$ is also square, and if $N/3$ is a cube, so is $(N\cdot x^{30})/3$, and if $N/5$ is a fifth power, so is $(N\cdot x^{30})/5$, is true for all $x$.

In the worked example, we include a final row, for all $x$, where the power of $x$ is a multiple of 2, 3, 5, and 7, and therefore satisfies all of the conditions above.

If we wish to further add $N/7$ as a seventh power, then we would need to look for some set where $2 | (a-1, b, c, d)$, $3 | (a, b-1, c, d)$, etc. This means that eg $b, c, d$ are even, $a, c, d$ are multiples of 3, etc. Here, we write the modulus in list form, where the modulus is taken over the corresponding point in the mod function.

We see that in the first row, $a$ must give a remainder of 0, when dividided by 3, 5, 7, so it must be a multiple of the product of $3 \cdot 5 \cdot 7$, that leaves a remainder of $1$, when divided by $2$.

• a = 1, 0, 0, 0, mod(2, 3, 5, 7), is a multiple of 105, gives $a=105$
• b = 0, 1, 0, 0, mod(2, 3, 5, 7), is a multiple of 70, gives $b=70$
• c = 0, 0, 1, 0, mod(2, 3, 5, 7), is a multiple of 42, gives $c=126$
• d = 0, 0, 0, 1, mod(2, 3, 5, 7), is a multiple of 30, gives $d=120$
• e = 0, 0, 0, 0, mod(2, 3, 5, 7), is a multiple of 210, gives $e=210$

So we can write this as $2^{105} 3^{70} 5^{126} 7^{120} x^{210}$, for all values of $x$. Note that we don't need to write $x^{210y}$, since the range of $x$ already includes $x^y$.

• can you show your workings please? How do you find out the general form of this number? – Dave Clifford Jun 14 '13 at 8:59
• @DaveClifford: I added a practical approach to using chinese remainders on an exponential scale. – wendy.krieger Jun 14 '13 at 10:07
• can you please explain further about this: "Since all of these are done modulo 30, which is always square, cube and fifth power, ie 30=lcm(2,3,5), we can append any x30 to this, including x=2 for example." ? – Dave Clifford Jun 14 '13 at 10:23
• I finally understand! Thanks for your generous help! – Dave Clifford Jun 14 '13 at 10:56
• @wendy.krieger In the later problem, you obtained the value of $c$ as $126$ which is $42*3$. How did you find that $3$ is the required multiplicand? Is there any procedure to find in general case? – SARTHAK GUPTA Jan 31 '18 at 10:04

I think the hint was meant to be used like this :

If $N$ is such a number, then $7^{30}N$ is another such number. Hence if you can get one solution, you get infinitely many solutions.

• Not necessarily. CRT only gives solutions in the exponents up to multiples of $2\cdot3\cdot5$, so solutions of the form $2^\alpha3^\beta5^\gamma$ suffice in exhibiting an infinite number of examples. Though of course appending multiples of $a^{30}$ for $(a,30)=1$ on the side helps in determining all solutions. – anon Jun 14 '13 at 8:01
• How was the a^30 is found? – Dave Clifford Jun 14 '13 at 9:36

Hint: Since you are dealing with some factors of $2,3,5$ it is reasonable to look for the solution in the form $N=2^{\alpha}3^{\beta}5^{\gamma}.$ The condition, that $N/2$ is a perfect square leads to $\alpha-1=0(\mod 2),$ $\beta=0(\mod 2)$ and $\gamma=0(\mod 2).$ Do the same for the other powers too.

• I totally agree with that! But does this answer suffice to prove there are infinite solutions? Or is there a proof by contradiction? And is there any relationship between the hint and the question? – Dave Clifford Jun 14 '13 at 7:50
• @DaveClifford: Have you tried following this hint to its logical conclusion? If you do, you will find explicitly an infinite number of solutions (which is the relationship of the hint to the question). Try to solve for $\alpha,\beta,\gamma$ using the chinese remainder theorem. – anon Jun 14 '13 at 8:03

I've seen this recently. Here is my solution. Let $$n$$ be of form, $$n=2^\alpha 3^\beta 5^\gamma$$. Note that,

• $$n/2$$ being perfect square implies $$\alpha\equiv 1\pmod{2}$$, $$\beta,\gamma\equiv 0\pmod{2}$$.
• $$n/3$$ being perfect cube implies $$\alpha\equiv 0\pmod{3}$$, $$\beta\equiv 1\pmod{3}$$, and $$\gamma\equiv 0\pmod{3}$$.
• Finally, $$n/5$$ being perfect fifth power implies $$\alpha\equiv 0\pmod{5}$$, $$\beta\equiv 0\pmod{5}$$, and $$\gamma\equiv 1\pmod{5}$$.

Thus, we are looking for triples $$(\alpha,\beta,\gamma)$$ obeying the conditions above simultaneously. However, for each element (say $$\alpha$$), we have three congruences with modulo coprime numbers, therefore, by Chinese remainder theorem, there exists infinitely many such triples, thus, infinitely many such $$n$$'s.