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.

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.

share|improve this question

1 Answer 1

up vote 4 down vote accepted

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.

share|improve this answer
    
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. –  Douglas S. Stones Oct 15 '10 at 2:01

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.