Maths Olympiad Prep

Library / /18 of 23

, 2025

Number theory Difficulty 4.1 AIME Prove it Canada

The prime factorization of 784784 is 2×2×2×2×7×72\times2\times2\times2\times7\times7 or
24×722^4\times7^2, and so 784784 is a perfect square because it can be
written in the form (22×7)×(22×7)(2^2\times7)\times(2^2\times7). The prime
factorization of 4545 is 32×53^2\times5, and so 4545 is not a perfect square. However,
45×545\times5 is a perfect square since
45×5=32×52=(3×5)×(3×5)45\times5=3^2\times5^2=(3\times5)\times(3\times5).

What are all positive integers jj with $j \leq
20forwhich for which 23×32×2^3\times 3^2\times
j$ is a perfect square?
Determine all positive integers kk so that 20×k20\times k is both a perfect square and a
divisor of 36003600.
Determine the number of ordered triples
of positive integers (a,b,c)(a, b, c) so
that $a2×b2×\$a^2\times b^2\times
c=2025$.

Solution

A positive integer n>1n>1 is
a perfect square exactly when the exponent on each prime factor in the
prime factorization of nn is
even.

We note that 23×322^3\times3^2 has an
odd exponent on the prime factor 2, and an even exponent on the prime
factor 33.

Thus, 23×32×j2^3\times3^2\times j is a
perfect square exactly when jj is
equal to the product of an odd number of factors of 22 and an even number of each additional
prime factor greater than 22
(including possibly having no additional prime factors).

Since j20j\leq20, then the prime
factorization of jj must contain
either one factor of 22 or three
factors of 22, and jj cannot contain five or more factors of
22 since 25>202^5>20.

When j=2j=2, the given product, 23×32×2=24×32=(22×3)×(22×3)2^3\times3^2\times2=2^4\times3^2=(2^2\times3)\times(2^2\times3),
is a perfect square.

When j=23=8j=2^3=8, the given product,
23×32×23=26×32=(23×3)×(23×3)2^3\times3^2\times2^3=2^6\times3^2=(2^3\times3)\times(2^3\times3),
is also a perfect square.

Is it possible for the prime factorization of jj to contain one 22 and an even number of another prime
factor greater than 22?

The smallest prime number greater than 22 is 33, and when j=2×32=18<20j=2\times3^2=18<20, the given product
23×32×2×32=24×34=(22×32)×(22×32)2^3\times3^2\times2\times3^2=2^4\times3^4=(2^2\times3^2)\times(2^2\times3^2),
is a perfect square.

The next smallest possible value of jj for which its prime factorization
contains exactly one 2 is 2×522\times5^2, which is greater than 2020. (Note that j=2×34j=2\times3^4 is also greater than 2020.)

The next smallest possible value of jj for which its prime factorization
contains exactly three factors of 22
is 23×322^3\times3^2, which is also
greater than 2020.

Therefore, the positive integers jj
which satisfy the given conditions are 22, 88
and 1818.
Since 3600=6023600=60^2 and 60=22×3×560=2^2\times3\times5, then 3600=(22×3×5)2=24×32×523600=(2^2\times3\times5)^2=2^4\times3^2\times5^2.

Thus, each divisor of 36003600 contains
at most the prime factors 22, 33 and 55, and cannot contain any other prime
factors.

Further, the prime factorization of each divisor of 36003600 contains at most four factors of
22, two factors of 33, and two factors of 55.

Suppose that k=2x×3y×5zk=2^x\times3^y\times5^z. Then $20×k=22×5×2x×3y×5z=2x+2×3y×5z+1$\$20\times k=2^2\times5\times2^x\times3^y\times5^z=2^{x+2}\times3^y\times5^{z+1}\$
is a divisor of 3600=24×32×523600=2^4\times3^2\times5^2 exactly when
0x20\leq x\leq 2, 0y20\leq y\leq 2, and 0z10\leq z\leq 1, for integers x,y,zx,y,z.

As noted in part (a), $20×k=2x+2×3y×5z+1$\$20\times k=2^{x+2}\times3^y\times5^{z+1}\$ is a perfect square exactly
when each of the exponents, x+2x+2,
yy, and z+1z+1 is even.

Since 0x20\leq x\leq 2, then x+2x+2 is even when x=0x=0 or x=2x=2.

Since 0y20\leq y\leq 2, then yy is even when y=0y=0 or y=2y=2.

Since 0z10\leq z\leq 1, then z+1z+1 is even when z=1z=1.

There are 22 choices for xx, 22
choices for yy, and 1 choice for
zz, and so there are 2×2×1=42\times2\times1=4 possible values of
kk.

When (x,y,z)=(0,0,1)(x,y,z)=(0,0,1), we get k=20×30×51=5k=2^0\times3^0\times5^1=5.

When (x,y,z)=(0,2,1)(x,y,z)=(0,2,1), we get k=20×32×51=45k=2^0\times3^2\times5^1=45.

When (x,y,z)=(2,0,1)(x,y,z)=(2,0,1), we get k=22×30×51=20k=2^2\times3^0\times5^1=20.

When (x,y,z)=(2,2,1)(x,y,z)=(2,2,1), we get k=22×32×51=180k=2^2\times3^2\times5^1=180.

The positive integers kk satisfying
the given conditions are 55, 4545, 2020, and 180180.
Since 2025=4522025=45^2 and 45=32×545=3^2\times5, then 2025=(32×5)2=34×522025=(3^2\times5)^2=3^4\times5^2.

Since a2a^2 and b2b^2 are perfect squares, and a2×b2×c=2025a^2\times b^2\times c=2025, then a2a^2 and b2b^2 are each equal to perfect square
divisors of 20252025.

The perfect square divisors of 2025=34×522025=3^4\times5^2 are: 1, 323^2, 343^4, 525^2, 32×523^2\times5^2, and 34×523^4\times5^2.

We count the number of ordered triples of positive integers (a,b,c)(a,b,c) by considering the following
22 cases: (1)(1) At least one of a2a^2 or b2b^2 is equal to 11; (2)(2) Both a2a^2 and b2b^2 are not equal to 11.

Case 1: At least one of a2a^2 or b2b^2 is equal to 11.

Suppose that a2=1a^2=1. Then b2b^2 can be equal to each of the perfect
square divisors of 20252025 previously
listed.

That is, b2b^2 can be equal to each
of the 66 values: 11, 323^2, 343^4, 525^2, 32×523^2\times5^2, and 34×523^4\times5^2.

For each of these values of b2b^2,
c=2025a2×b2c=\dfrac{2025}{a^2\times b^2}. For
example, when a2=1a^2=1 and b2=1b^2=1, then c=34×521×1=34×52c=\dfrac{3^4\times5^2}{1\times 1}=3^4\times5^2, and so (a,b,c)=(1,1,34×52)(a,b,c)=(1,1,3^4\times5^2) is a possible
ordered triple.

When a2=1a^2=1 and b2=32b^2=3^2, then $c=34×521×32=32×52\$c=\dfrac{3^4\times5^2}{1\times 3^2}=3^2\times5^2,andso, and so (a,b,c)=(1,3,32×52)$(a,b,c)=(1,3,3^2\times5^2)\$ is a possible
ordered triple.

Continuing in this way with a2=1a^2=1,
we get the following 6 ordered triples (a,b,c)(a,b,c): (1,1,34×52),(1,3,32×52),(1,32,52),(1,5,34),(1,3×5,32),(1,32×5,1)(1,1,3^4\times5^2), (1,3,3^2\times5^2), (1,3^2,5^2), (1,5,3^4), (1,3\times5,3^2), (1,3^2\times5, 1) For
each of the ordered triples above, with the exception of (1,1,34×52)(1,1,3^4\times5^2), we get a new ordered
triple by switching aa and bb.

Each of these 55 new ordered triples
can be determined by letting b2=1b^2=1
and following the process above, and thus each satisfies the given
conditions.

There are a total of 5×2+1=115\times2+1=11
ordered triples in this case.

Case 2: Both a2a^2 and b2b^2 are not equal to 11.

If one of a2a^2 or b2b^2 is equal to 34×523^4\times5^2, then the other must be
equal to 11 (since 2025=34×522025=3^4\times5^2).

In Case 2, both a2a^2 and b2b^2 are not equal to 11, and so each is also not equal to 34×523^4\times5^2.

Removing these from our list of perfect square divisors, the possible
values of a2a^2 and b2b^2 that remain are: 323^2, 343^4, 525^2, and 32×523^2\times5^2.

If a2=32a^2=3^2, then b2b^2 can be equal to 323^2 or 525^2 or 32×523^2\times5^2.

If a2=34a^2=3^4, then b2b^2 can be equal to 525^2.

If a2=52a^2=5^2, then b2b^2 can be equal to 323^2 or 343^4.

And finally, if a2=32×52a^2=3^2\times5^2,
then b2b^2 can be equal to 323^2.

In each case, the value of cc can be
determined as it was in Case 1.

Doing so gives the following 77
ordered triples (a,b,c)(a,b,c): (3,3,52),(3,5,32),(3,3×5,1),(32,5,1),(5,3,32),(5,32,1),(3×5,3,1)(3,3,5^2), (3,5,3^2), (3,3\times5,1), (3^2,5,1), (5,3,3^2), (5,3^2, 1),(3\times5,3,1) The number of ordered
triples of positive integers (a,b,c)(a,b,c) so that a2×b2×c=2025a^2\times b^2\times c=2025is 11+7=1811+7=18.

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

Source: CEMC, University of Waterloo, licensed CC-BY-NC-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.