Exercise 2.8.28* (A Theorem on partitions of the set of positive integers(Dyer-Bennet))

Proof.

$(\mathit{ii})\Rightarrow (i).$ By (ii), if $a$ is any integer and $s$ is any positive integer, $a^j\equiv a^{j+\mathit{sn}}(\mathit{mod}n)$, thus

In particular, for every positive integer $s$,

Assume for contradiction that $n$ is not square-free, so that $n=p^{2}m$ for some prime $p$ and some integer $m$. If we take $a=p,s=1$ in (1), we obtain

but this is impossible, since $p^2\nmid p(p^n-1)$. Therefore $n$ is square-free.

Since $n$ is square-free, $n=p_1{p}_2\cdots p_l$, where $p_1,p_2,\dots ,p_l$ are distinct primes. Mimicking the Demazure’s proof (see the second solution of Problem 27), let $a_i$ be a primitive root modulo $p_i$ for each index $i$. By the Chinese Remainder Theorem, there is some integer $a$ such that $a\equiv a_i(\mathit{mod}{p}_i)$ for all $i$. By (1) with $s=1$, $a(a^n-1)\equiv 0(\mathit{mod}n)$. A fortiori, $a(a^n-1)\equiv 0(\mathit{mod}{p}_i)$. Therefore $a_i(a_i^n-1)\equiv 0(\mathit{mod}{p}_i)$. Since $a_i$ is a primitive root modulo $p_i$, $a_i\wedge p_i=1$, thus

Since the order of $a_i$ is $p_i-1$, $p_i-1\mid n$ for all $i$. This proves (i).

$(i)\Rightarrow (\mathit{ii}).$ Conversely, suppose that $n$ is square-free and $(p-1)\mid n$ for all primes $p$ dividing $n$. Let $p$ be any prime factor of $n$, and let $a$ be any integer.

• If $p\nmid a$, by Fermat’s Theorem, $a^{p-1}\equiv 1(\mathit{mod}p)$. Since $p-1\mid n$, $a^n\equiv 1(\mathit{mod}p)$. Therefore, for all positive integers $s$, $a^{\mathit{sn}}\equiv 1(\mathit{mod}n)$, thus

  $$a(a^{\mathit{sn}}-1)\equiv 0(\mathit{mod}p).$$

• If $p\mid a$, $a\equiv 0(\mathit{mod}p)$, thus

  $$a(a^{\mathit{sn}}-1)\equiv 0(\mathit{mod}p).$$

This shows that for every prime factor $p$ of $n$, $a(a^n-1)\equiv 0(\mathit{mod}p).$ Since $n=p_1{p}_2\cdots p_l$ is square-free,

for every integer $a$. This proves (1).

Now if $j\ge 1$, $a^j(a^{\mathit{sn}}-1)=a^{j-1}[a(a^{\mathit{sn}}-1]\equiv 0(\mathit{mod}n)$. Therefore, for every positive integers $j,s$,

This shows that for every positive integer $k>j$ such that $k\equiv j(\mathit{mod}n)$, then

By exchanging the roles of $j$ and $k$, this is also true if $k<j$ (and also if $k=j$). Thus

□