Let $2\lt m\in \mathbb N$ and $\{r_1,r_2,...,r_{\phi(m)}\}$ be a reduced residue system modulo $m$. I want to find a necessary and sufficient condition for $k$ such that the set $\{r_1+k,r_2+k,...,r_{\phi(m)}+k\}$ be a reduced residue system modulo $m$ to.

I now that:

Theorem: if $c_1,c_2,\ldots,c_{\varphi(m)}$ be the reduced residue set modulo $m>2$, then $$c_1+c_2+\cdots+c_{\varphi(m)} \equiv 0 \pmod{m}$$ (see here)

We want to the set $\{r_1+k,r_2+k,...,r_{\phi(m)}+k\}$ be a reduced residue system modulo $m$. So, by above theorem: $$r_1+k+r_2+k+...+r_{\phi(m)}+k\equiv 0 \pmod{m}$$ Because of the set: $\{r_1,r_2,...,r_{\phi(m)}\}$ is a reduced residue system modulo $m$, $$r_1+r_2+...+r_{\phi(m)}\equiv 0 \pmod{m}$$ So, we should have: $k\phi(m) \equiv 0 \pmod{m}$. Thus, the necessary condition is that: $k\phi(m) \equiv 0 \pmod{m}$. Is this condition sufficient? if not, what is the sufficient condition?


The condition $k\phi(m) \equiv 0 \bmod{m}$ is not sufficient.

Take $m=6$ and $k=3$.

Then $k\phi(m) = 3\cdot 2 \equiv 0 \bmod{m}$ but $\{1,5\}$ is a reduced residue system modulo $6$ and $\{1+3,5+3\} \equiv \{4,2\}$ is not a reduced residue system modulo $6$.

Some other examples are $m=10, k=5$ and $m=12, k=3$.

More generally, if $m=2^e n$, with $n$ an odd, take $k=n$. Then $k\phi(m) =n 2^{e-1}\phi(n) \equiv 0 \bmod{m}$ because $\phi(n)$ is even. But $1+n$ is even and so is not a unit mod $m$.

The general case

Since the map $x\mapsto x+k$ is injective when considered as a map on $\mathbb Z/m$, it will induce a permutation of $U(m)$ if it sends units to units. So, the real question is:

When does $x\mapsto x+k$ preserve units mod $m$ ?

I don't have a complete proof right now, the answer seems to be this:

$x\mapsto x+k$ preserves units mod $m$ iff $k$ is a multiple of $\operatorname{rad}(m)$.

Here is a proof of one direction.

Take $k=tr$, a multiple of $r=\operatorname{rad}(m)$. Let $u$ be a unit and consider $u+k=u+tr$. If a prime divisor of $m$ divided $u+tr$, then it would divide $u$, which it doesn't. So $u+k$ is a unit whenever $u$ is unit.

I'd love to see a proof of the other direction.

As a consequence, there are no $k\ne0$ if $m$ is squarefree, because then $\operatorname{rad}(m)=m$ and $k \equiv 0 \bmod m$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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