Problem
ALG-B3-M06-P020 A Functional Equation Modulo a Prime
Let \(p\) be an odd prime and let \(f:\mathbb Z/p\mathbb Z\to\mathbb Z/p\mathbb Z\) satisfy \(f(x+f(y))=f(x)+y\) for all residues \(x,y\). Find \(f\).
Repeat the chain: injectivity, \(f(0)=0\), additivity.
With \(x=0\), \(f(f(y))=f(0)+y\). If \(f(a)=f(b)\), then \(f(f(a))=f(f(b))\), hence \(a=b\); the function is injective. On a finite set it is bijective. With \(y=0\), \(f(x+f(0))=f(x)\), so \(f(0)=0\). Thus \(f(f(y))=y\).
Put \(y=f(t)\): \(f(x+t)=f(x)+f(t)\). Hence \(f\) is additive on \(\mathbb Z/p\mathbb Z\), so \(f(x)=ax\). From \(f(f(x))=x\), we get \(a^2\equiv1\pmod p\). Since \(p\) is an odd prime, \(a\equiv1\) or \(a\equiv-1\). The answer is \(f(x)=x\) and \(f(x)=-x\) modulo \(p\).
Final task of the stage: discrete version of the injectivity-surjectivity method.