Problem:
For any positive integer a,Ο(a) denotes the sum of the positive integer divisors of a. Let n be the least positive integer such that Ο(an)β1 is divisible by 2021 for all positive integers a. Find the sum of the prime factors in the prime factorization of n.
Solution:
If a has prime factorization p1Ξ±1ββp2Ξ±2βββ―, then Ο(a)=Ο(p1Ξ±1ββ)Ο(p2Ξ±2ββ)β― and hence Ο(an)=Ο(p1nΞ±1ββ)Ο(p2nΞ±2ββ)β―. Therefore it suffices to find the least positive integer n such that Ο(pnΞ±)β‘1(mod2021) for all prime powers pΞ±. Because 2021=43β
47, by the Chinese Remainder Theorem, it is sufficient that Ο(pnΞ±)β‘1(mod43) and Ο(pnΞ±)β‘1(mod47) for all prime powers pΞ±.
Assume that n satisfies the required condition. In particular, for all p and Ξ±,n must satisfy
Ο(pnΞ±)=1+p+p2+β―+pnΞ±β‘1(modq),
where q=43 or q=47.
- If p=q, this sum will always be congruent to 1(modq).
- If pβ‘1(modq), then each term in the sum is 1(modq), so
Ο(pnΞ±)β‘nΞ±+1β‘1(modq)
Thus the required n must satisfy qβ£nΞ± for all Ξ±, so qβ£n.
Note that 43β
4+1=173 and 47β
6+1=283 are both prime numbers, so such p exist for both q=43 and q=47.
- If p is a prime such that pξ =q and gcd(pβ1,q)=1, then
1+p+p2+β―+pnΞ±=pβ1pnΞ±+1β1ββ‘1(modq)
which, after clearing the denominators and canceling a factor of p, reduces to
pnΞ±β‘1(modq).
By Fermat's Little Theorem, it is sufficient to have qβ1β£n. However, for both q=43 and q=47 there exists a prime p such that p is a primitive root modulo q. For example, p=5 is a primitive root modulo both 43 and 47. Therefore the condition that qβ1β£n is also necessary.
It follows that n must be divisible by 42,43,46, and 47 . The requested sum is 2+3+7+23+43+47=125.