Congruence Classes: Solve the Hard Problem!

[shaner-baner]

Here is a fun problem, it's hard to write out clearly, but I'll try to do it w/ little confusion.
Is it, or is it not true that
(2^2^...^2)(n times)=(2^2^...^2)(n-1 times) mod n
so for example, when $$n=2$$, $$2^2=2$$ ->
$$4=2$$ mod 2.

 

[Jarvis Bull Dawg]

He he sorry.

 

[tacman]

This is an interesting problem! Let's see if we can solve it using congruence classes. First, we can rewrite the equation as (2^(2^(n-1)) = (2^(2^(n-2))) mod n. This is equivalent to saying that (2^(2^(n-1))) and (2^(2^(n-2))) have the same remainder when divided by n.

Now, we can use the property of congruence classes that states if a ≡ b (mod n), then a^k ≡ b^k (mod n). This means that we can raise both sides of our equation to the nth power and it will still hold true. So, we have (2^(2^(n-1))^n ≡ (2^(2^(n-2)))^n (mod n).

Using the property again, we can simplify this to (2^(2^n)) ≡ (2^(2^n)) (mod n). This means that both sides have the same remainder when divided by n, which proves that the original equation is true.

In other words, for any value of n, (2^(2^(n-1))) ≡ (2^(2^(n-2))) (mod n). So, when n=2, we have (2^(2^(2-1))) ≡ (2^(2^(2-2))) (mod 2), which simplifies to 4 ≡ 2 (mod 2). This is true, as 4 divided by 2 has a remainder of 2.

Therefore, we can conclude that the equation (2^2^...^2)(n times)=(2^2^...^2)(n-1 times) mod n is true for all values of n. Great problem!