2
$\begingroup$

I thought I would post (as a puzzle) one of my favourite results in combinatorics. I actually use variants of this result in research quite often. It's not impossible that someone will post an unexpected proof that could be used in future research. But even if that does not occur, I hope it will be a fun exercise.

An orthomorphism of the cyclic group $\mathbb{Z}_n$ is a permutation $\sigma:\mathbb{Z}_n \rightarrow \mathbb{Z}_n$ such that $i \mapsto \sigma(i)-i$ is also a permutation.

Prove that orthomorphisms of $\mathbb{Z}_n$ exist if and only if $n$ is odd.

Actually, one direction is easy: $\sigma(i)=2i$ is an orthomorphism of $\mathbb{Z}_n$ when $n$ is odd. So what's left is to prove the non-existence of orthomorphisms of $\mathbb{Z}_n$ when $n$ is even.

1 Answers 1

4

I suppose you are talking about the additive group $\mathbb{Z}_n$ (i.e. the numbers modulo $n$).

Maybe I am missing something, but...

If $n$ is even then $\sum_{i=1}^{n} i \ne 0 \mod n$. So if $\sigma(i) -i$ were a permutation we would have that $\sum_{i=1}^{n} (\sigma(i) - i) \ne 0 \mod n$, but it is $0$ as $\sigma(i)$ is a permutation too.

  • 0
    Yep, this proof was originally given by Euler: L. Euler, Recherches sur une nouvelle espece de quarres magiques, Verh. Zeeuwsch. Gennot. Weten. Vliss., 9 (1782), 85--239. Enestrom E530, Opera Omnia OI7, 291--392.2010-10-15