Let $n>1$ be an integer, and let $k$ be the number of distinct prime divisors of $n$. Prove that there exists an integer $a$, $1<a<\frac{n}{k}+1$, such that $n \mid a^2-a$.
Problem
Source: China TST 2011 - Quiz 3 - D1 - P2
Tags: modular arithmetic, number theory proposed, number theory
21.05.2011 11:43
Posted here But it was really hard to get this by search.
22.05.2011 05:21
Solution by Zhero and me. Let $A$ denote the set of solutions to $n|a^2-a$ (consider this set $\pmod{n}$), and say that $n=p_1^{e_1}\cdots p_k^{e_k}$. Define $t_i$ such that \[t_i\equiv1\pmod{p_i^{e_i}}\]and \[t_i\equiv0\pmod{n/p_i^{e_i}}.\]By CRT (in a similar fashion to Lagrange interpolation), the $2^k$ distinct solutions of $a\in\{0,1\}\pmod{p_i^{e_i}}$ for $1\le i\le k$ (i.e. $a\in A$) form the set \[{A\equiv\{\sum\epsilon_i t_i}\}_{\epsilon_i\in\{0,1\}}\pmod{n}.\]In particular, $a\in\{0,1\}\pmod{n}$ iff $\epsilon_1=\cdots=\epsilon_k$. (*) Note that $a\in A\Longleftrightarrow n+1-a\in A$, so defining \[I_j=((j-1)\frac{n}{k},j\frac{n}{k}]\]for $1\le j\le k$, it suffices to show that $\sum\epsilon_i t_i\pmod{n} \in I_1\cup I_k$ for some choice of $\epsilon_i$ not all equal (so that $a\not\in\{0,1\}\pmod{n}$). Assume otherwise, and consider the partial sums $s_i=t_1+\cdots+t_i$ for $1\le i\le k$. Suppose that $s_u,s_v\in I_j$ for some $j$ and $u>v$. Then $s_u-s_v\in A$ and $s_u-s_v\in I_1\cup I_k$ while $s_u-s_v=t_{v+1}+\cdots+t_u\not\in\{0,1\}\pmod{n}$ according to (*), contradicting our assumption. Hence $s_1,\ldots,s_k$ lie in distinct intervals. But $I_1,\ldots,I_k$ are the only intervals, so there must be some $s_j\in I_1$, another contradiction.
26.05.2018 16:48
The case $k = 1$ is clear, so assume $k \ge 2$ and let $q_1, \dots, q_k$ be the prime powers in the factorization of $n$. Define the numbers $s_0, \dots, s_k$ in $[0, n-1]$ by the congruences \[s_i \equiv \begin{cases}1 \pmod{q_j} & \text{for } j \le i\\ 0 \pmod{q_j} & \text{for } j > i \end{cases}.\]Then both $a = s_j - s_i \pmod{n}$ and $a = 1 - s_j + s_i \pmod{n}$ (for $j > i$) satisfy $n \mid a(a - 1)$. (Note $s_0 = 0$ and $s_k = 1$.) It follows that if $s_j - s_i$ is in the segment $(-\tfrac{n}{k}, \tfrac{n}{k} + 1)$ of $\mathbb{Z}/n\mathbb{Z}$, then one of these two $a$ values will satisfy the conclusion. Thus it is sufficient to show that some two of $s_0, \dots, s_k$ (other than $s_0$ and $s_k$) are less than $n/k$ apart modulo $n$. Suppose not: then $s_0, \dots, s_{k-1}$ are equally spaced modulo $n$, as are $s_1, \dots, s_k$. But then $s_0 \equiv s_k \pmod{n}$, a contradiction.
10.07.2023 11:57
When $k=1$, take $a=n$ and we are done. From now on, assume that $k$ is at least $2$. Suppose that $n=\prod\limits_{i=1}^{k}{p_i}$, where $p_1,\dots,p_k$ are powers of distinct prime numbers. Due to Chinese Remainder Theorem, we are able to pick an integer $M_i$ satisfying $M_i\equiv 1 \pmod{p_i} \text{ and } M_i\equiv 0 \pmod{\prod\limits_{j\neq i}p_j}$ for each index $1\leq i\leq k$. Consider the following $k$ numbers: $$0,M_1,M_1+M_2,\dots,M_1+\dots+M_{k-1}$$Among them there would be two that are close, i.e. there exits an integer $l$ with $1\leq |l|\leq n/k$ and $1\leq i\leq j\leq k-1$, such that $$S:=\sum\limits_{t=i}^{j}M_t\equiv l \pmod{n}$$If $l>0$, then we take $a\equiv S \pmod{n}$ and $1\leq a\leq n$, otherwhise we take $a\equiv 1-S \pmod{n}$ and $1\leq a\leq n$. It is easy to check that in these cases $1<a<\frac{n}{k}+1$ and $n$ divides $a(a-1)$. Done!