Find the smallest possible number of divisors a positive integer $n$ may have, which satisfies the following conditions: 1. $24 \mid n+1$; 2. The sum of the squares of all divisors of $n$ is divisible by $48$ ($1$ and $n$ are included).
Problem
Source: Bulgarian Autumn Tournament 2023, 11.3
Tags: number theory
20.11.2023 00:27
Answer:$48$. Example:There are many examples, one of them is $47^{47}$, for instance. The sum of all divisors' squares of $n=p_1^{\alpha_1}...p_k^{\alpha_k}$ is equal to \[(p_1^{2\alpha_1}+p_1^{2\alpha_1-2}+...+1)...(p_k^{2\alpha_k}+p_1^{2\alpha_k-2}+...+1)\]We can assume that $2|\sum{p_i^{2\alpha_i-2j}}$ or $3|\sum{p_i^{2\alpha_i-2j}}$ because if $\sum{p_i^{2\alpha_i-2j}}$ is coprime with $48$, then we can delete $p_i$ on $n$ and get a less number of divisors. We know that $p_i\neq 2,3$. Claim: $\sum{p_i^{2\alpha_i-2j}}\equiv \alpha_i+1(mod \ 3)$ Proof: $p_i^{2m}\equiv 1(mod \ 3)\implies \sum{p_i^{2\alpha_i-2j}}\equiv 1+1+...+1\equiv \alpha_i+1 (mod \ 3)$ So $\boxed{3|\alpha_j+1}$ for some $j$. Let $S$ be the set of $\sum{p_i^{2\alpha_i-2j}}$ such that $N\in S\implies 16|\Pi{N}$ which means all the sums are even in $S$. $N$ is an element of $S$. Claim:If $2|N$, $N=\sum{p_i^{2\alpha_i-2j}}\equiv \alpha_i+1(mod\ 2)$ Proof:$p_i^{2m}\equiv 1(mod\ 2)\implies \sum{p_i^{2\alpha_i-2j}}\equiv 1+1+...+1\equiv \alpha_i+1(mod\ 2)$ Claim:If $4|N$, then $N=\sum{p_i^{2\alpha_i-2j}}\equiv \alpha_i+1(mod\ 4)$ Proof:$p_i^{2m}\equiv 1(mod\ 4)\implies \sum{p_i^{2\alpha_i-2j}}\equiv 1+1+...+1\equiv \alpha_i+1(mod\ 4)$ Claim:If $8|N$, then $N=\sum{p_i^{2\alpha_i-2j}}\equiv \alpha_i+1(mod\ 8)$ Proof:$p_i^{2m}\equiv 1(mod\ 8)\implies \sum{p_i^{2\alpha_i-2j}}\equiv 1+1+...+1\equiv \alpha_i+1(mod\ 8)$ Claim:If $16|N$, then $N=\sum{p_i^{2\alpha_i-2j}}\equiv \alpha_i+1(mod \ 16)$ Proof: $p_i^{2m}\equiv 1,9(mod \ 16)$ If $p_i^{2m}\equiv 1(mod \ 16)$, then it's the same idea with $(mod\ 3)$. If $p_i\equiv 9(mod\ 16)$, then $\sum{p_i^{2\alpha_i-2j}}\equiv 9^{\alpha_i}+...+9+1(mod \ 16)$ There exists $16|9^{\alpha_i}+...+1$ $\alpha_i$ is odd$\implies$ $\alpha_i\equiv 15(mod \ 16)$ $\alpha_i$ is even$\implies$ $16$ doesn't divide it. So $N\in S \implies 16|\Pi{N}$ gives us that $\boxed{16|\Pi{\alpha_i+1}}$ for $p_i^{\alpha_i}$ in $\sum{p_i^{2\alpha_i-2j}}\in S$ So $48|(\alpha_1+1)...(\alpha_k+1)$ which gives us that there are at least $48$ divisors of $n$. Note: If $\alpha$ in $3|\alpha_i+1$ and $2^l|\alpha_j+1$ the same, then the result doesn't change.