Maths Olympiad Prep

Library / /89 of 520

Number theory Difficulty 5.6 AIME, harder Find the answer

For a positive integer nn that is not a power of two, we define t(n)t(n) as the greatest odd divisor of nn and r(n)r(n) as the smallest positive odd divisor of nn that is not equal to 1. Determine all positive integers nn that are not powers of two and for which

n=3t(n)+5r(n) n=3 t(n)+5 r(n)

A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.

Solution

When nn is odd, t(n)=nt(n)=n so 3t(n)3 t(n) is greater than nn, contradiction. If nn is divisible by 2 but not by 4, then t(n)=12nt(n)=\frac{1}{2} n and 3t(n)3 t(n) is again greater than nn, contradiction again. We can conclude that nn must be divisible by 4 at least. If nn is divisible by 16, then t(n)116nt(n) \leq \frac{1}{16} n. Furthermore, r(n)t(n)r(n) \leq t(n), so 3t(n)+5r(n)8t(n)12n<n3 t(n)+5 r(n) \leq 8 t(n) \leq \frac{1}{2} n < n, contradiction. Therefore, nn is not divisible by 16. We can thus write n=4mn=4 m or n=8mn=8 m with m3m \geq 3 odd.

Suppose n=4mn=4 m with m3m \geq 3 odd. Then t(n)=mt(n)=m, so 4m=3m+5r(n)4 m=3 m+5 r(n), hence 5r(n)=m5 r(n)=m. Since r(n)r(n) is equal to the smallest odd prime divisor of nn, which is also the smallest prime divisor of mm, mm must be of the form m=5pm=5 p with p5p \leq 5 an odd prime number. Thus, m=15m=15 or m=25m=25, which gives n=60n=60 or n=100n=100. Both solutions are valid.

Suppose n=8mn=8 m with m3m \geq 3 odd. Again, t(n)=mt(n)=m, so 8m=3m+5r(n)8 m=3 m+5 r(n), hence 5r(n)=5m5 r(n)=5 m, or r(n)=mr(n)=m. We see that mm is prime. Thus, n=8pn=8 p with pp an odd prime number. This family of solutions is also valid.

We find the solutions to be n=60,n=100n=60, n=100 and n=8pn=8 p with pp an odd prime number.

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: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.