Olympiad Maths Prep

Track / Stage 6 / 62 of 400 #1062 of 2000

Problem 1062

National olympiad, first round
Number theory Difficulty 6.1 Prove it

Question 16 Let f(x)=3x+2f(x)=3x+2, prove that mN\exists m \in \mathbf{N}, such that f[100](m)f^{[100]}(m) is divisible by 1988.
(1988 Chinese National Training Team)

This one wants a proof. Work it on paper, read the official solution, then mark yourself honestly — the ladder only means something if the record is true.

Official solution

Proof 1 First find the fixed point, f(x)=3x+2,f(x)=x,x0=1,f(x)f(x)=3 x+2, f(x)=x, x_{0}=-1, f(x)
+1=3(x+1).f[2](x)+1=3(f(x)+1)=32(x+1),,f[100](x)+1=3100(x+1). \begin{array}{l} +1=3(x+1) . \\ f^{[2]}(x)+1=3(f(x)+1)=3^{2}(x+1), \cdots, f^{[100]}(x)+1 \\ =3^{100}(x+1) . \end{array}

The problem to be proved easily becomes: mN\exists m \in \mathbf{N}, such that 1988/3100(m+1)11988 / 3^{100}(m+1)-1, i.e., to prove
3100(x+1)1988y=1 3^{100}(x+1)-1988 y=1

has integer solutions for x,yx, y, and xNx \in \mathbf{N}.
Since (3100,1988)=1\left(3^{100}, 1988\right)=1, the above equation has integer solutions.
Let (x0,y0)\left(x_{0}, y_{0}\right) be one of the integer solutions, then
{x=x0+1988t,y=y0+3100t \left\{\begin{array}{l} x=x_{0}+1988 t, \\ y=y_{0}+3^{100} t \end{array}\right.

are also integer solutions, where tt is any integer. Clearly, we can take tt large enough to make x0+1988tNx_{0}+1988 t \in \mathbf{N}. Let x=mx=m at this time, then 1988f[100](m)1988 \mid f^{[100]}(m).
Note For the indeterminate equation sxty=1s x-t y=1, if (x0,y0)\left(x_{0}, y_{0}\right) is a solution of the equation, then
{x=x0+tk,y=y0+sk(kZ) \left\{\begin{array}{l} x=x_{0}+t k, \\ y=y_{0}+s k \end{array} \quad(k \in \mathbf{Z})\right.

are all solutions of the indeterminate equation.
If (s,t)=1(s, t)=1, then there must be a solution.
Proof 2 From Proof 1, we know
f[100](n)=3100(x+1)1, f^{[100]}(n)=3^{100}(x+1)-1,

So we only need to prove that there exists nN+n \in \mathbf{N}^{+}, such that
3100(n+1)1(mod4×7×71.) 3^{100}(n+1) \equiv 1(\bmod 4 \times 7 \times 71 .)

Take n+1=3mn+1=3^{m}, consider whether there exists mm, such that 3100+m1(mod4×7×71)3^{100+m} \equiv 1(\bmod 4 \times 7 \times 71). By Fermat's Little Theorem 36k1(mod7)370k=1(mod71)3^{6 k} \equiv 1(\bmod 7) 3^{70 k}=1(\bmod 71), and 32k1(mod4)3^{2 k} \equiv 1(\bmod 4). Therefore, take 100+m=[2k,6k,70k]=210k100+m=[2 k, 6 k, 70 k]=210 k. Taking m=210k100m=210 k-100 meets the requirement.

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