Here's how I would do it (you can fill in the details): Proceed by (strong) induction on m. If m=1 then it's trivial (everything is 0 mod 1!) If m is composite with at least 2 prime factors, use Chinese Remainder Theorem with two relatively prime factors of m. If m is a power of 2, it's trivial (sequence eventually becomes 0 mod m) If m is a power of an odd prime p, use fact that $2^{m(1-\frac{1}{p})} \equiv 1\,(\text{mod}\, m)$, and that if a = b (mod r) and 2^r = 1 (mod m), then 2^a = 2^b (mod m).

Here's something interesting: $2$ is in no way special .

Thanks, DPatrick! Your way makes a lot sense to me. I will try again and see if I could write it out. I have a couple of more problems that I need help with. I will post them soon.

DPatrick wrote: Here's how I would do it (you can fill in the details): Proceed by (strong) induction on m. If m=1 then it's trivial (everything is 0 mod 1!) If m is composite with at least 2 prime factors, use Chinese Remainder Theorem with two relatively prime factors of m. If m is a power of 2, it's trivial (sequence eventually becomes 0 mod m) If m is a power of an odd prime p, use fact that $2^{m(1-\frac{1}{p})}\equiv 1\,(\text{mod}\, m)$, and that if a = b (mod r) and 2^r = 1 (mod m), then 2^a = 2^b (mod m). How would you apply CRT here? How does one derive that fact you use? Could you explain your use of it more?

The fact is Euler's Theorem. And for the CRT part, prove more generally: if a sequence $a_{n}$ gets eventually periodic $\mod x$ and $\mod y$, both coprime, then it gets periodic $\mod xy$.

By constant, does that mean "periodic" or "all the same number"?

All the same, but in proving the above, you can show that the period is at worst the product of these periods. For the given case (constant, thus period = 1), this is a bit easier to show, even without CRT: Assume that $a_{n}= a_{n+1}\mod x,y$, thus that $x,y | a_{n+1}-a_{n}$. Since $x,y$ are coprime, we get $xy|a_{n+1}-a_{n}$, meaning nothing else than $a_{n}\equiv a_{n+1}\mod xy$. We know that the assumption is true for all big $n$, thus the result is also true for big $n$.

Can someone provide a full proof for this by also explaining how CRT is used since I do not even know what it is.

Here is a more detailed explanation: One way is to apply strong induction on $n$ (I assume you know what strong induction is). Obviously when $n$ is a power of two, the hypothesis holds (everything must eventually become 0 mod n). A version of the Chinese Remainder Theorem asserts that the system of congruency: $x = a_1 mod n_1$ $x = a_2 mod n_2$ . . $x = a_k mod n_k$ has a unique solution mod $n_1n_2..n_k$ given that $n_i$ are pairwise relatively prime. For example, $x = 3 mod 5$ $x = 2 mod 3$ has a unique solution $x = 8 mod 15$. How do we construct a solution? We can write $x=5k+3$ so then $5k +3 = 2 mod 3$ so $5k = 2 mod 3$. Because 5 is relatively prime to 3, there is guaranteed to exist a unique solution k solving this. Here we find k = 1 mod 3. So let k = 3r+1 then we get x=$15r+8$. Why is the CRT relevant to the problem? Well say the sequence becomes constant for $x,y$ for large enough $n$, and $x,y$ are coprime. i.e $a_i = c_1 mod x$ and $a_i = c_2 mod y$ for $i \geq N$. We can immediately show that the sequence $a_i$ is constant mod $xy$ after $N$ as well. If $i \geq N$, then $a_i = c_1 mod x$ and $a_i = c_2 mod y$. By the CRT, $a_i = c_3 mod xy$ for some $c_3$ so it is also constant mod $xy$. So the point is that if $n$ is a number that can be decomposed into a product of two relatively prime numbers then apply the above argument to show that the sequence is periodic mod $n$. The only $n$ for which this cannot work are $n=p^k$ for some positive integer $k$. Now if $k=1$, by fermat's little theorem $a^{p-1} = 1$ mod $p$ and note here that $p-1=r$ is even. Either $r$ is a power of two or $r$ is the product of a power of two and an odd number greater than 1. If $k\geq 2$, we may apply euler's theorem which says that $a^{\phi(n)} = 1 mod n$, where the $\phi(n)$ counts how many positive integers less than $n$ are relatively prime to it. So $\phi(p^k) = p^k(1-1/p) = p^{k-1}(p-1) = r$. Observe that $p^{k-1}$ and $p-1$ are relatively prime (remember p>2). Note that $r<n$. The point is that to determine $a_k$ mod n, we really need only to look at $a_{k-1}$ mod r. This is because $a_k = 2^{a_{k-1}}$ and $2^r = 1$ mod $n$. Well because in any case $r$ satisfies these cases we've already covered (it's either a product of two relatively prime numbers so we can use CRT, or it's a power of 2). So then $a_{k}$ becomes constant mod r which implies it becomes constant mod $n$. Note: The tower of twos could've been replaced with any other number. Modifying the proof a bit would fix it. Note: we don't need CRT here as Zeta pointed out.

PenguinIntegral wrote: DPatrick wrote: Here's how I would do it (you can fill in the details): Proceed by (strong) induction on m. If m=1 then it's trivial (everything is 0 mod 1!) If m is composite with at least 2 prime factors, use Chinese Remainder Theorem with two relatively prime factors of m. If m is a power of 2, it's trivial (sequence eventually becomes 0 mod m) If m is a power of an odd prime p, use fact that $2^{m(1-\frac{1}{p})}\equiv 1\,(\text{mod}\, m)$, and that if a = b (mod r) and 2^r = 1 (mod m), then 2^a = 2^b (mod m). How would you apply CRT here? How does one derive that fact you use? Could you explain your use of it more? the 1st fact he uses is evident from euler's theorem.for the next fact, you can simply get using the definition of congruence that a-b=rk . m divides 2^(r)-1 so, m divides 2^(rk)-1 and hence the fact.

It is easy to see that $a \equiv b\pmod{\phi(n)}$ simply means $2^a \equiv 2^b\pmod{n}$ So the original sequence will eventually be constant if and only if the sequence $1,2,2^2,2^{2^2} \dots\pmod{\phi(n)}$ is eventually constant which means $0,1,2,2^2,2^{2^2}\dots \pmod{\phi(\phi(n))}$ is eventually constant. It is easy to see that a time will come when $\phi^t(n)$ will eventually be 1,no matter how large n is.At this point the sequence will be $0$,i.e., constant modulo 1.So the original statement is true. This is also essentially the solution to grobber's generalization.

sayantanchakraborty wrote: It is easy to see that $a \equiv b\pmod{\phi(n)}$ simply means $2^a \equiv 2^b\pmod{n}$ If $n$ is even, you also need $a,b$ to be big enough ($\geq v_2(n)$ suffices). And it's not completely easy to see: you need to split $n$ into the part coprime to $2$ and the part with prime factors dividing $2$ (written in a way that works for arbitrary numbers instead of $2$).

For storage. Define the sequence $(a_k)_{k \ge 1}$ such that $a_1=2$ and for all $k,$ we have $a_{k+1}=2^{a_k}$. Since $2^{v_2(n)} \mid a_{\ell}$ for all large $\ell$ we may assume that $n$ is odd. By Euler's Theorem, for all $k$ large enough, $$a_k \equiv a_{k-1} \pmod{\phi(n)} \Longrightarrow a_{k+1} \equiv a_k \pmod{n}.$$ By induction, we can show that $$a_{k-j+1} \equiv a_{k-j} \pmod{\phi^j(n)} \Longrightarrow a_{k+1} \equiv a_k \pmod{n}.$$ Since $\left(\phi^j(n)\right)_{j \ge 1}$ is a strictly decreasing sequence of positive integers, it is eventually identically equal to $1$. Consequently, the last implication holds and the result follows.

We proceed with strong induction. Notice that for $n=1$, $a_i\equiv 0$ mod $1$ for all $i$. Now suppose there is a value $n$ such that for all positive integers $k\leq n$, the sequence is eventually constant. If $n+1=p_1^{b_1}p_2^{b_2}...p_j^{b_j}$ for $j\geq 2$, then we know it becomes constant mod $p_1^{b_1},p_2^{b_2},...,p_j^{b_j}$, so by CRT it also becomes constant mod $n+1$. If $n+1=2^k$ for positive $k$, then we can see that eventually all the terms in the sequence will become $0$ mod $2^k$. Finally, if $n+1=p^k$ for odd $p$ and positive $k$, then since $\phi(n+1)<n+1$, we know that the sequence will become constant mod $\phi(n)$. Since the exponents of the sequence are the same as the actual sequence and since $\gcd(2,n+1)=1$, by Euler's Totient the sequence mod $n+1$ will also become constant, completing the inductive step.

Philomath_314 wrote:

The "rigorous", mathematical way to writeup the "continue this process" forever is basically induction so you know, it isn't really different from the induction solutions.

starchan wrote: Philomath_314 wrote:

The "rigorous", mathematical way to writeup the "continue this process" forever is basically induction so you know, it isn't really different from the induction solutions. Nah, induction needs a proof. It doesn't. Because it's only continuing the process until we arrive at a result.

Philomath_314 wrote: starchan wrote: Philomath_314 wrote:

The "rigorous", mathematical way to writeup the "continue this process" forever is basically induction so you know, it isn't really different from the induction solutions. Nah, induction needs a proof. It doesn't. Because it's only continuing the process until we arrive at a result. Induction essentially does that but writes it up in a more clean way? I'm sorry I don't understand what you are trying to say here.