Function Conjunction. Topic: Number Theory. Level: Olympiad.

Problem: (2002 MOP Homework - #4) Given an odd prime $ p $, find all functions $ f: \mathbb{Z} \rightarrow \mathbb{Z} $ satisfying the following two conditions:

$ (i) $ $ f(m) = f(n) $ for all $ m, n \in \mathbb{Z} $ such that $ m \equiv n \pmod{p} $;
$ (ii) $ $ f(mn) = f(m)f(n) $ for all $ m, n \in \mathbb{Z} $.

Solution: We claim that the only such functions are $ f(n) = 0 $ for all $ n $, $ f(n) = 1 $ for all $ n $, or $ f(n) = 1 $ for $ n \not\equiv 0 \pmod{p} $ and $ f(n) = 0 $ for $ n \equiv 0 \pmod{p} $.

Note that by condition $ (i) $ it is sufficient to define $ f $ for one complete residue class modulo $ p $ (because all the other values are then determined).

Assume $ n \not\equiv 0 \pmod{p} $ for this. Let

$ k = max(|f(1)|, |f(2)|, \ldots, |f(p-1)|) $.

Since $ \{1, \ldots, p-1\} $ form a complete residue class modulo $ p $ (except $ 0 $), by condition $ (i) $ we know that $ f(n) $ takes only the values $ f(1), f(2), \ldots, f(p-1) $. Therefore

$ k = max(|f(n)|) $ for $ n \not\equiv 0 \pmod{p} $.

Suppose $ k > 1 $. Let $ a $ be the value for which $ |f(a)| = k $. Then we have

$ |f(a^2)| = |f(a)f(a)| = k^2 > k $

(and $ a^2 $ cannot be divisible by $ p $). But then $ k $ is not the maximum value as defined. Contradiction.

So $ k = 0, 1 $.

For the case $ k = 0 $, we simply have $ f(n) = 0 $ for all $ n \not\equiv 0 \pmod{p} $. Then $ f(0) = f(n)f(0) = 0 $ as well, giving us the solution $ f(n) = 0 $ for all $ n $.

For the case $ k = 1 $, there exists an $ a \not\equiv 0 \pmod{p} $ such that $ |f(a)| = 1 $. Then

$ f(a^2) = f(a)f(a) = 1 $.

But since $ (a^2,p) = 1 $, we have that $ a^2 $ is a primitive root modulo $ p $ and therefore the set $ \{a^2, a^4, \ldots, a^{2p-2}\} $ forms a complete residue class (except $ 0 $), but clearly all of these are $ 1 $ (by $ (ii) $) so $ f(n) = 1 $ for all $ n \not\equiv 0 \pmod{p} $. And

$ f(0) = f(0)f(0) \Rightarrow f(0) = 0,1 $,

both of which work. So our solutions are $ f(n) = 1 $ for all $ n $ or $ f(n) = 1 $ for $ n \not\equiv 0 \pmod{p} $ and $ f(n) = 0 $ for $ n \equiv 0 \pmod{p} $.

And the claim is proved. QED.

--------------------

Comment: The most fun part of this problem was getting it down to $ k = 0,1 $. Then it was just sort of tedious casework (though with some cool number theory) to find out all the possible functions.

--------------------

Practice Problem: (WOOT Test 7 - #4) Find all functions $f$ defined on the rational numbers such that $f(1) = 2$ and

$f(xy) = f(x)f(y) - f(x + y) + 1$

for all rational numbers $x$ and $y$.