Let $f(x) = 3x + 2.$ Prove that there exists $m \in \mathbb{N}$ such that $f^{100}(m)$ is divisible by $1988$.
Problem
Source: China TST 1988, problem 5
Tags: number theory unsolved, number theory
27.06.2005 18:39
It's easy to show that $f^n(x)=9^nx+2\sum_{i=0}^{n-1}3^i=9^nx+3^n=3^n(3^nx+1)$ (for instance by induction). Because $gcd(3^{100},1988)=1$ thus taking $x=-(3^{100})^{-1}$ $(\mod 1988)$ we get infinitely many such $m$.
27.06.2005 18:55
I think you missed a $-1$ in the computation, so that in fact $f^n(x) = 3^n(x+1)-1.$ Anyway, the idea is the same by choosing $x = -1 + 3^{-100} \mod [1988].$ Pierre.
27.06.2005 19:12
yes indeed, thanks
28.06.2005 12:46
I used the obvious lemma: $a, b, c$ are positive integers, if $(a, b) = 1$, then $am + c$ (mod $b$) are all distinct for $m = 1, 2, \ldots, b$. Thus, let $m = 1, 2, \ldots, 1988$, which are all distinct (mod $1988$), since 3 is prime, $(3, 1988) = 1$, then using the lemma. We have $f(1), f(2), \ldots, f(1988)$ are all distinct (mod $1988$), that is a permutation of $1, 2, 3, ..., 1988$. Repeat above disscusion 100 times, then the conclusion follows easily: Among $f^{100}(1), f^{100}(2), \ldots, f^{100}(1988)$, just one value is divisible by 1988. By the way, from the above solution, we can say the minimum value of $m$ satisfying the condition is no larger than 1988.
29.06.2005 01:41
It isn't a particularly hard problem but that's a very beautiful way to do it. It looks to me like the other answers get a solution < 1989 as well.