Given a prime number \( p \geq 3 \) and a positive integer \( m \), find the smallest positive integer \( n \) with the following property: for every positive integer \( a \), which is not divisible by \( p \), the sum of the natural divisors of \( a^n \) greater than 1 is divisible by \( p^m \).
Problem
Source: XIII International Festival of Young Mathematicians Sozopol 2024, Theme for 10-12 grade
Tags: number theory
13.09.2024 21:57
I made up this problem by generalizing as much as possible the ideas from AIME 2021/14. This was among the most appreciated problems by the contestants overall. Let's first choose \( a \equiv 1 \pmod{p^m} \) to be a prime (such exists by Dirichlet's theorem). We want the sum \( a + a^2 + \cdots + a^n \) to be divisible by \( p^m \). Here each term gives a remainder of 1, so the sum is congruent to \( n \), meaning \( n \) must be divisible by \( p^m \). Next, let us choose \( a \equiv g \pmod{p} \) to be a prime number, where \( g \) is a primitive root modulo \( p \) (such a root exists for \( p \geq 3 \) and \( a \) exists by Dirichlet's theorem). Since \( g \not\equiv 0, 1 \), we have \( \gcd(a, p) = \gcd(a - 1, p) = 1 \), and thus the sum \( a + a^2 + \cdots + a^n \) is divisible by \( p \) if and only if (after dividing by \( a \) and multiplying by \( a - 1 \)) the number \( a^n - 1 \equiv g^n - 1 \) is divisible by \( p \). Since the order of \( g \) is \( p-1 \), we obtain that \( n \) must be divisible by \( p-1 \). Conversely, we show that \( n = p^m(p-1) \) works for any \( a \). For \( a = \prod_{i=1}^s q_i^{e_i} \), we want \( \prod_{i=1}^s(1 + q_i + q_i^2 + \cdots + q_i^{ne_i}) \equiv 1 \pmod{p^m} \). We will prove, in fact, that each factor gives a remainder of 1. Since \( a \) is not divisible by \( p \) by assumption, we have \( p \neq q_i \) for every \( i \). If \( p \) does not divide \( q_i - 1 \), then \[ q_i + q_i^2 + \cdots + q_i^{ne_i} = \frac{q_i((q_i^{e_i})^n - 1)}{q_i - 1} \]is divisible by \( p^m \) by Euler's theorem, since \( n = p \varphi(p^m) \). If \( p \) divides \( q_i - 1 \), then (since \( p \neq 2 \)) by Lifting the exponent lemma we compute \[ \nu_p(q_i + q_i^2 + \cdots + q_i^{ne_i}) = \nu_p(1 + q_i + \cdots + q_i^{ne_i-1}) = \nu_p(q_i^{ne_i} - 1) - \nu_p(q_i - 1) = \nu_p(ne_i) \geq m \]and once again we have divisibility by \( p^m \).