## Wednesday, March 1, 2006

### 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$.

#### 1 comment:

1. Let x=1; then,
f(y) = f(1)*f(y) -f(x+1)+1 for all rational y, or
f(y)=2f(y)-f(x+1)+1 --> f(y+1)=f(y) + 1 for all rational y.

Since f(1)=2 and f(y+1)=f(y)+1 for all rational y, it follows with induction to both negative and positive integers that f(z)=z+1 for all integers z.

Furthermore, it follows by induction that
f(y+z)=f(y) + z for rational y and integer z.

Next, suppose x= 1/w and y=w for an integer w. Then,
f(1) = f(1/w)*f(w) - f(1/w + w) + 1
1=f(1/w)[w+1] - f(1/w) - w
f(1/w)[w]=w+1
f(1/w)=1/w+1 - again, for all integers w.

Finally, let x=m/n and y=n for some integers m and n. Then,
f(m)=f(m/n)f(n) - f(m/n + n) +1
m+1 = f(m/n)[n+1] - f(m/n) - n + 1
m+n=f(m/n)(n)
f(m/n)=(m+n)/n
f(m/n)=1+m/n for all integers m and n; so for all rationals R,
f(R)=1+R
is the only function that exists to satisfy these conditions.