Maths Olympiad Prep

Library / /13 of 13

Algebra Difficulty 7.0 National olympiad, round 2 Find the answer

Find all functions f:NNf : \mathbb{N}\rightarrow{\mathbb{N}} such that for all positive integers mm and nn the number f(m)+nmf(m)+n-m is divisible by f(n)f(n).

A number or a short expression. Spacing and $ signs are ignored.

Solution

Consider the functional equation where f:NN f : \mathbb{N} \rightarrow \mathbb{N} satisfies, for all positive integers m m and n n ,

f(m)+nm0(modf(n)). f(m) + n - m \equiv 0 \pmod{f(n)}.

This condition implies:

f(m)+nm(modf(n)). f(m) + n \equiv m \pmod{f(n)}.

We aim to find all such functions f f .

### Case 1: Linear Functions of the Form f(n)=n+c f(n) = n + c

Assume f(n)=n+c f(n) = n + c for some constant cN c \in \mathbb{N} . Substituting into the original equation, we have:

f(m)+nm=(m+c)+nm=n+c. f(m) + n - m = (m + c) + n - m = n + c.

This implies:

n+cm(modn+c). n + c \equiv m \pmod{n + c}.

The left-hand side is divisible by n+c n + c since:

n+cm0(modn+c), n + c - m \equiv 0 \pmod{n + c},

which is trivially true for any integer m m . Thus, f(n)=n+c f(n) = n + c is a valid solution.

### Case 2: Constant Function f(n)1 f(n) \equiv 1

Assume f(n)1 f(n) \equiv 1 . Substituting into the original equation, we have:

f(m)+nm0(mod1), f(m) + n - m \equiv 0 \pmod{1},

which simplifies to:

(m+nm)0(mod1), (m + n - m) \equiv 0 \pmod{1},

which is always true. Thus, f(n)=1 f(n) = 1 is a valid solution.

### Case 3: Piecewise Function f(even)=1,f(odd)=2 f(\text{even}) = 1, f(\text{odd}) = 2

Consider f(n)=1 f(n) = 1 for even n n and f(n)=2 f(n) = 2 for odd n n .

1. **n n is even**: f(n)=1 f(n) = 1 . The equation becomes:

f(m)+nm0(mod1), f(m) + n - m \equiv 0 \pmod{1},

which holds true since any number is divisible by 1.

2. **n n is odd**: f(n)=2 f(n) = 2 . The equation becomes:

f(m)+nm0(mod2). f(m) + n - m \equiv 0 \pmod{2}.

For any m m and odd n n , nm0(mod2) n - m \equiv 0 \pmod{2} as both n n and m m would have the same parity.

Thus, f(even)=1,f(odd)=2 f(\text{even}) = 1, f(\text{odd}) = 2 is a valid solution.

### Case 4: Piecewise Function f(odd)=1,f(even)=2 f(\text{odd}) = 1, f(\text{even}) = 2

Consider the similar argument for the reverse configuration:

1. **n n is odd**: f(n)=1 f(n) = 1 . The equation becomes:

f(m)+nm0(mod1), f(m) + n - m \equiv 0 \pmod{1},

which holds true.

2. **n n is even**: f(n)=2 f(n) = 2 . The equation becomes:

f(m)+nm0(mod2). f(m) + n - m \equiv 0 \pmod{2}.

For any m m and even n n , both n n and m m would have the same parity, thus maintaining divisibility.

Hence, f(odd)=1,f(even)=2 f(\text{odd}) = 1, f(\text{even}) = 2 is also a valid solution.

### Conclusion

The functions that satisfy the given conditions are:

f(n)=n+c,f(n)1,f(even)=1,f(odd)=2,f(odd)=1,f(even)=2. \boxed{f(n) = n + c}, \boxed{f(n) \equiv 1}, \boxed{f(\text{even}) = 1, f(\text{odd}) = 2}, \boxed{f(\text{odd}) = 1, f(\text{even}) = 2}.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.