PUMaC 2016 · 数论（B 组） · 第 6 题

PUMaC 2016 — Number Theory (Division B) — Problem 6

Compute the sum of the two smallest positive integers b with the following property: there 2 are at least ten integers 0 ≤ n < b such that n and n end in the same digit in base b . gcd( m,n ) 6 5 2 3

解析

The condition is equivalent to having n ( n − 1) ≡ 0 (mod b ), which means that every prime power dividing b divides either n or n − 1. The Chinese remainder theorem implies that the number of different values n for which this is the case is 2 to the power of the number of distinct primes dividing b , so at least four primes divide b . Thus, the smallest values of b are 2 · 3 · 5 · 7 and 2 · 3 · 5 · 11. Adding these up, we get 2 · 3 · 5 · 18 = 540 . Problem written by Eric Neyman.