Functional divisibility
-
- Posts:107
- Joined:Sun Dec 12, 2010 10:46 am
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.
Re: Functional divisibility
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.
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.
- Zero.
- Why?
- Because all the poles are in Eastern Europe.
Revive the IMO marathon.
Re: Functional divisibility
$f^{100}(n) = 3^{100}(n+1)-1$, and if the proposition is correct this too implies $3|1$.
Any corrections, Mim?
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
Use $L^AT_EX$, It makes our work a lot easier!
Nur Muhammad Shafiullah | Mahi
-
- Posts:107
- Joined:Sun Dec 12, 2010 10:46 am
Re: Functional divisibility
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.