Functional divisibility

For students of class 9-10 (age 14-16)
mutasimmim
Posts:107
Joined:Sun Dec 12, 2010 10:46 am
Functional divisibility

Unread post by mutasimmim » Tue Oct 21, 2014 11:04 pm

Given $f(n)=3n+2$, prove that there exists a natural number $n$ such that $f^{100}(n)$ is divisible by $1988$.
Last edited by mutasimmim on Wed Oct 22, 2014 8:16 pm, edited 1 time in total.

Nirjhor
Posts:136
Joined:Thu Aug 29, 2013 11:21 pm
Location:Varies.

Re: Functional divisibility

Unread post by Nirjhor » Wed Oct 22, 2014 5:44 pm

Really? :?

Clearly $f^{100}(n)=3^{100}n+a_{100}$ where $a_n=3a_{n-1}+2~\forall ~n\in\mathbb{N}$ and $a_1=2$. So we have to prove that $1998m-3^{100}n=a_{100}$ has natural solutions. But taking mod $3$ on both side shows that this is absurd as $3\mid 1998$ and $a_{100}=3a_{99}+2\equiv 2~(\bmod~3)$.

Anything wrong?

EDIT: (Solution for $1988$) Since $1988=2^2\times 7\times 71$, we have $\gcd\left(1988,3^{100}\right)=1$. So the equation $1988m - 3^{100}n=1$ has integral solutions, hence has positive integral solution for $n$. The result follows.
- What is the value of the contour integral around Western Europe?

- Zero.

- Why?

- Because all the poles are in Eastern Europe.


Revive the IMO marathon.

User avatar
*Mahi*
Posts:1175
Joined:Wed Dec 29, 2010 12:46 pm
Location:23.786228,90.354974
Contact:

Re: Functional divisibility

Unread post by *Mahi* » Wed Oct 22, 2014 7:59 pm

$f^{100}(n) = 3^{100}(n+1)-1$, and if the proposition is correct this too implies $3|1$.
Any corrections, Mim?
Please read Forum Guide and Rules before you post.

Use $L^AT_EX$, It makes our work a lot easier!

Nur Muhammad Shafiullah | Mahi

mutasimmim
Posts:107
Joined:Sun Dec 12, 2010 10:46 am

Re: Functional divisibility

Unread post by mutasimmim » Wed Oct 22, 2014 8:16 pm

Actually that would be $1988$ instead of $1998$. Corrected now. And I think it would be relevant to cite the source of this problem. its from Chinese TST 1988.

Post Reply