Let $n$ be a positive integer and $d(n)$ is the number of positive integer divisors of $n$. For every two positive integer divisor $x,y$ of $n$, the remainders when $x,y$ divided by $d(n)+1$ are pairwise distinct. Show that either $d(n)+1$ is equal to prime or $4$.
Problem
Source: Turkey JBMO TST 2024 P4
Tags: number theory
13.05.2024 20:57
Suppose otherwise. Clearly at most one remainder when divided by $d(n) + 1$ isn't taken by the divisors of $n$. Case 1: This remainder not taken is not zero. Then some divisor of $n$ is a multiple of $d(n) + 1$, so $d(n) + 1 \mid n$. However, if $n \ne d(n) + 1$, then $n, d(n) + 1$ are different divisors of $n$ that are $0 \pmod{d(n) + 1}$, absurd. Hence $n = d(n) + 1$, so it's easy to see that $n\in \{3, 4\}$ (because for larger $n$, both $n -1 $ and $n - 2$ don't divide $n$), which satisfy the conditions for $d(n) + 1$. Case 2: This remainder not taken is zero. If two distinct primes divide $d(n) + 1$, let $a,b$ be two relatively prime positive integers greater than $1$ multiplying to $d(n) + 1$. Clearly some divisor of $n$ is a multiple of $a$ and some divisor of $n$ is a multiple of $b$, so $a\mid n, b \mid n$, meaning $ab = d(n) + 1 \mid n$, absurd. Hence $d(n) + 1$ must be a prime power. Let $d(n) + 1 = p^k$ for some prime $p$ and positive integer $k > 1$. Now the number of divisors of $n$ that have a $\nu_p$ of $k - 1$ is just $p - 1$ ($p^{k-1}, 2p^{k-1},\ldots, (p-1)p^{k-1}$ modulo $p^k$), so $\frac{n}{p^{k-1}}$ has $p - 1$ divisors. Hence $p^k - 1 = d(n) = k (p-1) $. For $p > 2$ and $k > 1$, we have $p^{k-1} \ge 3^{k-1} > k$, so $p^k > pk > k(p-1) + 1$, so $p^k - 1 >k(p-1)$, absurd. Thus, $p = 2$. So $2^k - 1 = k\implies 2^k =k + 1 \implies k =1$, absurd. Hence we must have $d(n) + 1$ prime in this case.
13.05.2024 22:22
Let $\bar{d}(n):=d(n)+1$. I first show $\bar{d}(n)$ is a prime power. Suppose the contrary that $\textstyle\bar{d}(n) = \prod_{1\le I\le L}p_i^{e_i}$ where $p_1<\cdots<p_L$ are distinct primes, $e_i\ge 1$ and $L\ge 2$. Note that if the residue class zero is covered, then $\bar{d(n)}\mid n$. Unless $n=d(n)+1$, we thus obtain two divisors congruent modulo $\bar{d(n)}$, a contradiction. The case $n=d(n)+1$ is easily handled, using the well-known bound $d(n)\le 2\sqrt{n}$. So, the residue class zero must be not covered. But then, for any $1\le I\le L$, there is a $d_i$ such that \[ d_i\equiv p_i^{e_i}\pmod{\bar{d}(n)} \]Hence, $p_1,\dots,p_L\mid n$, but then $\bar{d(n)}\mid n$, a contradiction. So, $\bar{d(n)} = p^e$ for a prime $p$ and $e\ge 1$. We are done if $e=1$, so let $e\ge 2$. Suppose the residue class 0 is covered, so $p^e\mid n$. If $p^{e+1}\mid n$, we again obtain two divisors congruent to zero modulo $\bar{d}(n)$, a contradiction. Hence, $p^e\mid \mid n$. Moreover, if $n$ has a prime divisor $q\ne p$, then $qp^e\mid n$ too, but then both $p^e$ and $qp^e$ are zero modulo $\bar{d}(n)$, contradiction. So, $n=p^e$ and thus $d(n)+1=e+2=p^e$. For $p\ge 3$, Bernoulli inequality yields $p^e>e+2$ whereas for $p=2$ it is easily seen $(p,e)=(2,2)$ is the only solution. Lastly, assume $p^e\nmid n$, and thus $p^{e-1}\mid n$. Once again, $p^{e-1}\mid\mid n$. Set $n=p^{e-1}t$ where $(p,t)=1$ and let $q=d(t)$. Then, $n$ has $q$ divisors $d_i$ with $v_p(d_i)=e-1$. If $q>p$, then two of these divisors are congruent modulo $p^e$, a contradiction. So, $q\le p$. Lastly, $d(n) = ed(t)=qe$ and $qe+1 = p^e\le pe+1$. With simple bounds, no solutions besides $(p,e)=(2,2)$ again.