HMMT 二月 2007 · 冲刺赛 · 第 9 题

HMMT February 2007 — Guts Round — Problem 9

[ 7 ] I ponder some numbers in bed, 2 All products of three primes I’ve said, n = 37 · 3 . . . Apply φ they’re still fun: φ ( n ) = 3 now Elev’n cubed plus one. 11 + 1? What numbers could be in my head? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . th 10 HARVARD-MIT MATHEMATICS TOURNAMENT, 24 FEBRUARY 2007 — GUTS ROUND

解析

[ 7 ] I ponder some numbers in bed, 2 All products of three primes I’ve said, n = 37 · 3 . . . Apply φ they’re still fun: φ ( n ) = 3 now Elev’n cubed plus one. 11 + 1? What numbers could be in my head? Answer: 2007 , 2738 , 3122 . The numbers expressible as a product of three primes are each of 3 2 3 2 2 the form p , p q , or pqr , where p, q, and r are distinct primes. Now, φ ( p ) = p ( p − 1) , φ ( p q ) = 3 2 2 p ( p − 1)( q − 1) , and φ ( pqr ) = ( p − 1)( q − 1)( r − 1). We require 11 +1 = 12 · 111 = 2 3 37 . The first case is easy to rule out, since necessarily p = 2 or p = 3, which both fail. The second case requires p = 2 , p = 3 , 2 or p = 37 . These give q = 667 , 223, and 2, respectively. As 667 = 23 · 29 , we reject 2 · 667, but 2 2 3 233 = 2007 and 37 2 = 2738 . In the third case, exactly one of the primes is 2, since all other primes 2 are odd. So say p = 2. There are three possibilities for ( q, r ): (2 · 1+1 , 2 · 3 · 37+1) , (2 · 3+1 , 2 · 3 · 37+1) , 2 and (2 · 3 + 1 , 2 · 37 + 1). Those are (3 , 667) , (7 , 223) , and (19 , 75) , respectively, of which only (7 , 223) is a pair of primes. So the third and final possibility is 2 · 7 · 223 = 3122 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . th 10 HARVARD-MIT MATHEMATICS TOURNAMENT, 24 FEBRUARY 2007 — GUTS ROUND 2