# Finding every number which satisfies a remainder condition

Letting $n\in\mathbb N$, let us call an $n$ which satisfies the following condition "a good number".

Condition : Let $\{a_1,a_2,\cdots,a_n\}=\{1,2,\cdots,n\}$. Letting $b_i\ (i=1,2,\cdots,n)$ be the remainder when we divide $ia_i$ by $n$, there exists a set $(a_1,a_2,\cdots,a_n)$ such that $$\{b_1,b_2,\cdots,b_n\}=\{0,1,\cdots, n-1\}.$$

Then, here is my question.

Question : Can we find every good number?

Motivation : We can see both $1$ and $2$ are good numbers. By using computer, the numbers from $3$ to $18$ do not seem to be good numbers. However, I don't have any good idea in general. What I've got is the following theorem :

Theorem : For $k\in\mathbb N$, if $n=4k-2$ is a good number, then $\frac{(4k-3)!!}{2k-1}\equiv \left\{\frac{(4k-3)!!}{2k-1}\right\}^2\ \text{(mod$4k-2$)}$. Here, $(4k-3)!!=1\cdot 3\cdot 5\cdots (4k-5)\cdot (4k-3)$.

Proof for theorem : Letting $m=2k-1$, we can write $n=2m$. Since $m$ is odd, we know that if the remainder when we divide $ka_k$ by $2m$ is odd, then both $k$ and $a_k$ are odd. Hence, we know that if $k$ is odd, then $a_k$ is odd.

If $a_i=m$ for $i\not=m$ (note that $m$ is odd), then both $ia_i$ and $ma_m$ are odd multiples of $m$, which leads that $ia_i\equiv ma_m\equiv m\ \text{(mod$2m$)}$. This is a contradiction. Hence, we get $a_m=m$ and $ma_m\equiv m\ \text{(mod$2m$)}$.

Hence, $$\{a_1,3a_3,5a_5,\cdots,(m-2)a_{m-2},(m+2)a_{m+2},\cdots,(2m-1)a_{2m-1}\}=\{1,3,5,\cdots,m-2,m+2,\cdots,2m-1\}$$ leads \begin{align}a_1\cdot 3a_3\cdot 5a_5\cdots (m-2)a_{m-2}\cdot (m+2)a_{m+2}\cdots (2m-1)a_{2m-1}\equiv \frac{(2m-1)!!}{m}\qquad(1)\end{align} On the other hand, $$\{a_1,a_3,a_5,\cdots,a_{m-2},a_{m+2}, \cdots,a_{2m-1}\}=\{1,3,5,\cdots,m-2,m+2,\cdots,2m-1\}$$ leads $$a_1\cdot 3a_3\cdot 5a_5\cdots (m-2)a_{m-2}\cdot (m+2)a_{m+2}\cdots (2m-1)a_{2m-1}$$ $$\equiv 1\cdot 3\cdots (m-2)\cdot (m+2)\cdots (2m-1)\times \times a_1\cdot a_3\cdots a_{m-2}\cdot a_{m+2}\cdots a_{2m-1}$$ \begin{align}\equiv \frac{(2m-1)!!}{m}\times \frac{(2m-1)!!}{m}\qquad(2)\end{align}

Hence, $(1)(2)$ leads what we desire. Q.E.D.

This theorem tells us that $n=6,10,14$, for example, are not good numbers. However, the theorem tells us nothing about good numbers. Can anyone help?

Suppose that $n$ is a good number. For convenience, if $a_i=n$, we shall replace $n$ by $0$, so that $\{a_1, a_2, \ldots, a_n\}=\{0, 1, \ldots , n-1\}$. It is easy to see that this does not affect the definition of a good number.

For each divisor $d$ of $n$, define

$$A_d=\{a_i: \gcd(i, n)=d\}, B_d=\{b_i: \gcd(i, n)=d\}, C_d=\{i: 0 \leq i \leq n-1, \gcd(i, n)=d\}$$

Note that $|A_d|=|B_d|=|C_d|=\varphi(\frac{n}{d})$ for each divisor $d$ of $n$. Also note that $A_d$ are pairwise disjoint over all $d \mid n$, $B_d$ are pairwise disjoint over all $d \mid n$, $C_d$ are pairwise disjoint over all $d \mid n$.

Step 1: $B_d=C_d$ for all $d \mid n$.

We proceed by strong induction on the number of prime factors $k$ (counting multiplicity) of $\frac{n}{d}$.

When $k=0$, we have $\frac{n}{d}=1$ so $d=n$. Then $b_n \equiv na_n \equiv 0 \pmod{n}$ so $B_n=\{b_n\}=\{0\}=C_n$.

Suppose that the statement holds for $0 \leq k \leq j$. Consider $d$ s.t. $\frac{n}{d}$ has $j+1$ prime factors, counting multiplicity.

For each element $b_i \in B_d$, we have $d \mid i$, so $b_i \equiv ia_i \pmod{n}$ implies $d \mid \gcd(b_i, n)$.

If $\gcd(b_i, n) \not =d$, then write $\gcd(b_i, n)=ld, l>1$. Then $b_i \in C_{ld}$. Since $\frac{n}{ld}$ has $\leq j$ prime factors counting multiplicity, we have by the induction hypothesis that $C_{ld}=B_{ld}$. Thus $b_i \in B_{ld}$, which implies that $B_d \cap B_{ld} \not =\emptyset$, a contradiction.

Therefore we must have $\gcd(b_i, n)=d$, so that $b_i \in C_d$. Therefore $B_d \subseteq C_d$. Since they have the same size ($\varphi(\frac{n}{d})$), we get $B_d=C_d$.

We are thus done by strong induction.

Step 2: $A_d \subseteq \bigcup_{e \mid d}{C_e}$ for all $d \mid n$.

Consider $a_i \in A_d$. Then $b_i \equiv ia_i \pmod{n}$, and $b_i \in B_d$ so by Step $1$, $b_i \in C_d$, so $d=\gcd(b_i, n)=\gcd(ia_i, n)$.

Let $\gcd(a_i, n)=e$. Then $e \mid \gcd(ia_i, n)=d$. Therefore $a_i \in C_e$ for some $e \mid d$. Therefore we indeed have $A_d \subseteq \bigcup_{e \mid d}{C_e}$.

Step 3: $A_d=C_d$ for all $d \mid n$.

We proceed by strong induction on $s$, the number of prime factors of $d$, counting multiplicity.

When $s=0$, we have $d=1$. We have by Step $2$ that $A_1 \subseteq \bigcup_{e \mid 1}{C_e}=C_1$. Since $A_1$ and $C_1$ have the same size, we have $A_1=C_1$.

Suppose that the statement holds for $s=j$. The consider $d$ with $j+1$ prime factors, counting multiplicity.

We have by Step $2$ that $A_d \subseteq \bigcup_{e \mid d}{C_e}=C_d \cup \bigcup_{e \mid d, e \not =d}{C_e}$. Note that for all proper divisors $e$ of $d$, $e$ has at most $j$ prime factors counting multiplicity, so by the induction hypothesis $A_e=C_e$. Thus $A_d \subseteq C_d \cup \bigcup_{e\mid d, e \not =d}{A_e}$. Since $A_d$ and $A_e$ are disjoint for $e \not =d$, we get $A_d \subseteq C_d$. Since $A_d$ and $C_d$ have the same size, $A_d=C_d$.

We are thus done by strong induction.

Step 4: If $p$ is a prime factor of $n$, then $p=2$ and $p^2 \nmid n$.

Let $p$ be a prime factor of $n$. Write $n=pm$. Then by above, $A_m=B_m=C_m$.

If $p \mid m$, note that $b_m=ma_m \in B_m$, so $b_m \in C_m$, so

$$m=\gcd(b_m, n)=\gcd(ma_m, pm)=m\gcd(a_m, p)$$

Thus $\gcd(a_m, p)=1$, so $p \nmid a_m$. However $a_m \in A_m$ so $a_m \in C_m$ so $\gcd(a_m, n)=m$ so $m \mid a_m$ so $p \mid a_m$, a contradiction.

Therefore $p \nmid m$. This implies that $p^2 \nmid n$.

For a set $S$, denote $\prod_S$ as the product of all elements in $S$.

Since $A_m=B_m=C_m$, we have $\prod_{A_m}=\prod_{B_m}=\prod_{C_m}$.

For each $b_i \in B_m$, we have $\gcd(i, n)=m$ so $i \in C_m$ and $a_i \in A_m$. Since $b_i \equiv ia_i \pmod{n}$, we now get $\prod_{B_m} \equiv \prod_{A_m}\prod_{C_m} \pmod{n}$.

Thus

$$\prod_{C_m} \equiv \prod_{B_m} \equiv \prod_{A_m}\prod_{C_m} \equiv (\prod_{C_m})^2 \pmod{n}$$

In particular, $$\prod_{C_m} \equiv (\prod_{C_m})^2 \pmod{p}$$

However we have $$\prod_{C_m}=\prod_{i=1}^{p-1}{im}=m^{p-1}(p-1)! \equiv -1 \pmod{p}$$

using Fermat's little theorem and Wilson's theorem.

Therefore $(-1) \equiv (-1)^2 \pmod{p}$, so $p \mid 2$, so $p=2$

Conclusion: We see that $n$ cannot have any odd prime factors, so $n$ must be a power of $2$. Morever if $2 \mid n$, then $2^2 \nmid n$. Thus we are left with $n=1, 2$, which are easily checked to be good numbers.

• Great! Thank you very much. I'm really happy to read this answer. – mathlove Dec 1 '13 at 14:43