MathLabs

Problem 4

Prove that there is no function ff from the set of non-negative integers into itself such that f(f(n))=n+1987f(f(n)) = n + 1987 for every non-negative integer nn.
Step 2 of 5: Pass to residue classes
Previous stepNext step
In plain words

The second iterate is the identity on residue classes.

g:Z/1987Z→Z/1987Z,g([n])=[f(n)]g:\mathbb Z/1987\mathbb Z\to\mathbb Z/1987\mathbb Z,\qquad g([n])=[f(n)]
Detailed analysis

The relation f(n+1987)=f(n)+1987f(n+1987)=f(n)+1987 makes g([n])=[f(n)]g([n])=[f(n)] well defined. Also g(g([n]))=[f(f(n))]=[n]g(g([n]))=[f(f(n))]=[n], so gg is an involution.