Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
add comment

1 Answer 1

up vote 1 down vote accepted

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.

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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.