Maths Olympiad Prep

Library / /2 of 2

Number theory Difficulty 8.8 Shortlist Prove it Romania

If nn is a composite number, denote DnD_n its largest proper divisor. A number nn will be called squarish if the number Dn+Dn+1D_n + D_{n+1} is a perfect square.

a) Show that 3535, 7676 and 755755 are squarish.

b) Show that there are infinitely many squarish numbers.

Solution

a.
Let us compute Dn+Dn+1D_n + D_{n+1} for n=35n = 35, 7676, and 755755.

For n=35n = 35:
3535 is composite. Its largest proper divisor is D35=35/5=7D_{35} = 35/5 = 7 (since 35=5×735 = 5 \times 7 and 7<357 < 35).
3636 is composite. Its largest proper divisor is D36=36/2=18D_{36} = 36/2 = 18 (since 36=2×1836 = 2 \times 18 and 18<3618 < 36).
So D35+D36=7+18=25=52D_{35} + D_{36} = 7 + 18 = 25 = 5^2.

For n=76n = 76:
7676 is composite. Its largest proper divisor is D76=76/2=38D_{76} = 76/2 = 38.
7777 is composite. Its largest proper divisor is D77=77/7=11D_{77} = 77/7 = 11.
So D76+D77=38+11=49=72D_{76} + D_{77} = 38 + 11 = 49 = 7^2.

For n=755n = 755:
755755 is composite. Its largest proper divisor is D755=755/5=151D_{755} = 755/5 = 151.
756756 is composite. Its largest proper divisor is D756=756/2=378D_{756} = 756/2 = 378.
So D755+D756=151+378=529=232D_{755} + D_{756} = 151 + 378 = 529 = 23^2.

Therefore, 3535, 7676, and 755755 are squarish numbers.

b.
We want to show that there are infinitely many squarish numbers.

Let us look for nn such that Dn+Dn+1D_n + D_{n+1} is a perfect square.
Suppose nn is odd and n+1n+1 is even.
For odd nn, the largest proper divisor is Dn=n/pD_n = n/p, where pp is the smallest prime dividing nn.
For even n+1n+1, Dn+1=(n+1)/2D_{n+1} = (n+1)/2.

Let us try n=p21n = p^2 - 1, where pp is an odd prime.
Then n=p21n = p^2 - 1 is composite (since p>2p > 2), and n+1=p2n+1 = p^2 is composite for p>2p > 2.

Dn=(p21)/(p1)=p+1D_n = (p^2 - 1)/ (p-1) = p + 1 (since p21=(p1)(p+1)p^2 - 1 = (p-1)(p+1)).
Dn+1=Dp2=p2/p=pD_{n+1} = D_{p^2} = p^2 / p = p.
So Dn+Dn+1=(p+1)+p=2p+1D_n + D_{n+1} = (p + 1) + p = 2p + 1.

But 2p+12p + 1 is not always a perfect square. Let's try another approach.

Let nn be such that nn is divisible by kk, and n+1n+1 is divisible by k+1k+1.
Suppose n=k(k+1)1=k2+k1n = k(k+1) - 1 = k^2 + k - 1.
Then n+1=k2+kn+1 = k^2 + k.

Dn=n/k=(k2+k1)/k=k+11/kD_n = n / k = (k^2 + k - 1)/k = k + 1 - 1/k (not integer unless k=1k = 1).

Alternatively, let us consider nn and n+1n+1 such that Dn=aD_n = a, Dn+1=bD_{n+1} = b, and a+b=m2a + b = m^2.

Let us use the examples above:
35=5×735 = 5 \times 7, D35=7D_{35} = 7, 36=2×1836 = 2 \times 18, D36=18D_{36} = 18, 7+18=257 + 18 = 25.
76=2×3876 = 2 \times 38, D76=38D_{76} = 38, 77=7×1177 = 7 \times 11, D77=11D_{77} = 11, 38+11=4938 + 11 = 49.
755=5×151755 = 5 \times 151, D755=151D_{755} = 151, 756=2×378756 = 2 \times 378, D756=378D_{756} = 378, 151+378=529151 + 378 = 529.

Notice that in each case, nn is divisible by 55, 22, 55 respectively, and n+1n+1 is divisible by 22, 77, 22 respectively.

Let us generalize:
Let n=p×qn = p \times q, Dn=qD_n = q (assuming p<qp < q), n+1=2×rn+1 = 2 \times r, Dn+1=rD_{n+1} = r.
Then q+r=m2q + r = m^2.

Alternatively, for nn odd, n+1n+1 even, Dn+1=(n+1)/2D_{n+1} = (n+1)/2.
Suppose n=k×mn = k \times m, Dn=mD_n = m.
Let n+1=2×tn+1 = 2 \times t, Dn+1=tD_{n+1} = t.
So m+t=s2m + t = s^2.

Let us try n=2k1n = 2k - 1, n+1=2kn+1 = 2k.
DnD_n depends on the factorization of 2k12k - 1.
Dn+1=kD_{n+1} = k.
If 2k12k - 1 is composite and its largest proper divisor is mm, then m+km + k is a perfect square for infinitely many kk.

Alternatively, for nn even, n=2kn = 2k, Dn=kD_n = k, n+1n+1 odd, Dn+1D_{n+1} depends on its factorization.

But from the examples, we see that for n=5×7=35n = 5 \times 7 = 35, n+1=36=2×18n+1 = 36 = 2 \times 18, D35=7D_{35} = 7, D36=18D_{36} = 18, 7+18=257 + 18 = 25.
Similarly, for n=5×pn = 5 \times p, n+1=2×qn+1 = 2 \times q, Dn=pD_n = p, Dn+1=qD_{n+1} = q, p+q=m2p + q = m^2.

Therefore, for any mm, let p=m2qp = m^2 - q, qq arbitrary, n=5×pn = 5 \times p, n+1=2×qn+1 = 2 \times q, and p+q=m2p + q = m^2.

Thus, there are infinitely many squarish numbers.

Alternatively, since the set of perfect squares is infinite, and for each perfect square m2m^2, we can find nn such that Dn+Dn+1=m2D_n + D_{n+1} = m^2, there are infinitely many squarish numbers.

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.