Maths Olympiad Prep

Library / /488 of 860

Number theory Difficulty 5.2 AIME, harder Find the answer

I ponder some numbers in bed, all products of three primes I've said, apply ϕ\phi they're still fun: n=3723ϕ(n)=113+1?n=37^{2} \cdot 3 \ldots \phi(n)= 11^{3}+1 ? now Elev'n cubed plus one. What numbers could be in my head?

A number or a short expression. Spacing and $ signs are ignored.

Solution

The numbers expressible as a product of three primes are each of the form p3,p2qp^{3}, p^{2} q, or pqrp q r, where p,qp, q, and rr are distinct primes. Now, ϕ(p3)=p2(p1),ϕ(p2q)=\phi\left(p^{3}\right)=p^{2}(p-1), \phi\left(p^{2} q\right)= p(p1)(q1)p(p-1)(q-1), and ϕ(pqr)=(p1)(q1)(r1)\phi(p q r)=(p-1)(q-1)(r-1). We require 113+1=12111=22323711^{3}+1=12 \cdot 111=2^{2} 3^{2} 37. The first case is easy to rule out, since necessarily p=2p=2 or p=3p=3, which both fail. The second case requires p=2,p=3p=2, p=3, or p=37p=37. These give q=667,223q=667,223, and 2, respectively. As 667=2329667=23 \cdot 29, we reject 226672^{2} \cdot 667, but 32233=20073^{2} 233=2007 and 3722=273837^{2} 2=2738. In the third case, exactly one of the primes is 2, since all other primes are odd. So say p=2p=2. There are three possibilities for (q,r):(21+1,23237+1),(23+1,2337+1)(q, r):\left(2 \cdot 1+1,2 \cdot 3^{2} \cdot 37+1\right),(2 \cdot 3+1,2 \cdot 3 \cdot 37+1), and (232+1,237+1)\left(2 \cdot 3^{2}+1,2 \cdot 37+1\right). Those are (3,667),(7,223)(3,667),(7,223), and (19,75)(19,75), respectively, of which only (7,223)(7,223) is a pair of primes. So the third and final possibility is 27223=31222 \cdot 7 \cdot 223=3122.

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