Maths Olympiad Prep

Library / /29 of 37

Algebra Difficulty 8.2 Shortlist Find the answer

Let f:QQf : \mathbb Q \to \mathbb Q be a function such that for any x,yQx,y \in \mathbb Q, the number f(x+y)f(x)f(y)f(x+y)-f(x)-f(y) is an integer. Decide whether it follows that there exists a constant cc such that f(x)cxf(x) - cx is an integer for every rational number xx.

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

Solution

Let f:QQ f : \mathbb{Q} \to \mathbb{Q} be a function such that for any x,yQ x, y \in \mathbb{Q} , the number f(x+y)f(x)f(y) f(x+y) - f(x) - f(y) is an integer. We need to determine whether there exists a constant c c such that f(x)cx f(x) - cx is an integer for every rational number x x .

To address this, we construct a counter-example. We begin by recursively constructing a sequence k1,k2, k_1, k_2, \ldots with 0kq<q 0 \leq k_q < q for each q q , as follows:
1. k1=0 k_1 = 0 .
2. If q>1 q > 1 and k1,,kq1 k_1, \ldots, k_{q-1} are already defined, choose kq k_q such that 0kq<q 0 \leq k_q < q and kqkd(modd) k_q \equiv k_d \pmod{d} whenever a positive integer d d divides q q .
3. If q q is a prime, set kq=1 k_q = 1 if q=2 q = 2 or q1(mod73) q \equiv 1 \pmod{73} , and kq=2 k_q = 2 otherwise.

This construction is well-defined by induction. For the base case, k1=0 k_1 = 0 is trivial. For the induction step:
- If q q is not a prime, the Chinese Remainder Theorem ensures the existence of such a kq k_q if gcd(d1,d2)kd1kd2 \gcd(d_1, d_2) \mid k_{d_1} - k_{d_2} for any two distinct proper divisors d1,d2 d_1, d_2 of q q . From the induction hypothesis, kd1kd(modd) k_{d_1} \equiv k_d \pmod{d} and kd2kd(modd) k_{d_2} \equiv k_d \pmod{d} , implying kd1kd2(modd) k_{d_1} \equiv k_{d_2} \pmod{d} .
- If q q is a prime, the congruences kqk1(mod1) k_q \equiv k_1 \pmod{1} and kqkq(modq) k_q \equiv k_q \pmod{q} are trivially satisfied.

Next, we define f f for all rationals as f(pq)={pkqq} f\left(\frac{p}{q}\right) = \left\{\frac{pk_q}{q}\right\} , where {x} \{x\} denotes the fractional part of x x . This definition is well-defined because {pkqq}={pnkqnqn}={pkqnq} \left\{\frac{pk_q}{q}\right\} = \left\{\frac{pnk_{qn}}{qn}\right\} = \left\{\frac{pk_{qn}}{q}\right\} , and kqnkq(modq) k_{qn} \equiv k_q \pmod{q} implies pkqnpkq(modq) pk_{qn} \equiv pk_q \pmod{q} .

Given two rationals x x and y y , choose a common denominator r r and write x=Xr x = \frac{X}{r} and y=Yr y = \frac{Y}{r} . Then f(x+y)={(X+Y)krr} f(x+y) = \left\{\frac{(X+Y)k_r}{r}\right\} and f(x)+f(y)={Xkrr}+{Ykrr} f(x) + f(y) = \left\{\frac{Xk_r}{r}\right\} + \left\{\frac{Yk_r}{r}\right\} , and the difference between these numbers is an integer.

Assume there is a constant c c such that f(x)cx f(x) - cx is an integer for every rational x x . Since f(1)=0 f(1) = 0 , cZ c \in \mathbb{Z} . For every prime p p , kpcp \frac{k_p - c}{p} must be an integer. Since there are infinitely many primes 1(mod73) \equiv 1 \pmod{73} , c=1 c = 1 , and since there are infinitely many primes not congruent to 1(mod73) 1 \pmod{73} , c=2 c = 2 , leading to a contradiction.

Therefore, there does not exist a constant c c such that f(x)cx f(x) - cx is an integer for every rational number x x . The answer is: \boxed{\text{No}}.

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.