Problem:
Let m be a positive integer such that there are at least 50 positive integers x less than m for which x2β1 is a multiple of m. What is the sum of the digits of the least possible value of m?
Answer Choices:
A. 12
B. 15
C. 16
D. 18
E. 22
Solution:
Let N(m) be the number of x with 0β€x<m and x2β‘1(modm). For m>1, x=0 is never a solution, so N(m) counts exactly the positive integers x<m in the problem.
Counting solutions for prime powers.
- For an odd prime power pk: pkβ£(xβ1)(x+1), and p cannot divide both xβ1 and x+1 (they differ by 2). So xβ‘Β±1(modpk), giving exactly 2 solutions.
- For powers of 2: modulo 2 there is 1 solution (x=1), modulo 4 there are 2 (x=1,3), and modulo 2e with eβ₯3 there are 4 (x=Β±1, 2eβ1Β±1).
Combining. By the Chinese Remainder Theorem, if m=2ep1k1βββ―ptktββ with distinct odd primes piβ, then
N(m)=ceββ
2t,ceβ=β©βͺβͺβ¨βͺβͺβ§β124βeβ€1,e=2,eβ₯3.β
So N(m) is a power of 2, and N(m)β₯50 means N(m)β₯64.
Minimizing m. Raising an odd exponent above 1 does not add solutions, so the odd part should be a product of the smallest odd primes. The candidates with N(m)=64 are
eβ₯3, t=4:e=2, t=5:eβ€1, t=6:β8β
3β
5β
7β
11=9240,4β
3β
5β
7β
11β
13=60060,3β
5β
7β
11β
13β
17=255255.β
The least possible value is m=9240, and the sum of its digits is
9+2+4+0=(B) 15.
The problems and solutions on this page are the property of the MAA's American Mathematics Competitions