Show that, for any fixed integer n≥1, the sequence 2,22,222,2222,…(modn)is eventually constant. [The tower of exponents is defined by a1=2,ai+1=2ai. Also ai(modn) means the remainder which results from dividing ai by n.]
Problem
Source: USAMO 1991 #3
Tags: induction, modular arithmetic, strong induction, number theory, relatively prime, prime numbers, number theory unsolved
02.09.2004 20:22
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 2m(1−1p)≡1(modm), and that if a = b (mod r) and 2^r = 1 (mod m), then 2^a = 2^b (mod m).
02.09.2004 21:37
Here's something interesting: 2 is in no way special .
03.09.2004 01:45
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.
30.09.2006 19:55
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 2m(1−1p)≡1(modm), 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?
30.09.2006 20:08
The fact is Euler's Theorem. And for the CRT part, prove more generally: if a sequence an gets eventually periodic \mod x and \mod y, both coprime, then it gets periodic \mod xy.
30.09.2006 20:15
By constant, does that mean "periodic" or "all the same number"?
30.09.2006 20:22
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.
22.03.2011 19:32
Can someone provide a full proof for this by also explaining how CRT is used since I do not even know what it is.
22.03.2011 22:55
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.
26.05.2012 03:54
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.
20.07.2014 16:16
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.
10.10.2014 14:22
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).
10.03.2017 15:44
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.
10.03.2020 21:50
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.
28.02.2023 18:44
28.02.2023 19:03
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.
28.02.2023 19:10
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.
28.02.2023 19:17
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.