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.

    ReplyDelete