Cube root of unity with a huge exponent

[Saitama]

Problem:
Let $y=x/(1+x)$, where
$$\Large x=\omega^{2009^{2009^{\cdots \text{upto 2009 times}}}}$$
and $\omega$ is a complex root of 1. Then $y$ is

A)$\omega$

B)$-\omega$

C)$\omega^2$

D)$-\omega^2$

Attempt:
I somehow need to show that the huge exponent is of the form $3k$, $3k+1$ or $3k-1$ but I don't see how to do so.

Any help is appreciated. Thanks!

 

[Nono713]

Problem:
Let $y=x/(1+x)$, where
$$\Large x=\omega^{2009^{2009^{\cdots \text{upto 2009 times}}}}$$
and $\omega$ is a complex root of 1. Then $y$ is

A)$\omega$

B)$-\omega$

C)$\omega^2$

D)$-\omega^2$

Attempt:
I somehow need to show that the huge exponent is of the form $3k$, $3k+1$ or $3k-1$ but I don't see how to do so.

Any help is appreciated. Thanks!

This is really number theory. First observe that $2009 \equiv 2 \pmod{3}$. Therefore, for any integer $k$:
$$2009^k \equiv 2^k \pmod{3}$$
Furthermore, let $k = 2009^l$ for some integer $l$. Then $k$ is clearly odd, since $2009$ is odd. So:
$$k \equiv 2009^l \equiv 1^l \equiv 1 \pmod{2}$$
Through Euler's Theorem since $\varphi(3) = 2$ (actually the FLT suffices since $3$ is prime) we have:
$$2009^{(2009^l)} \equiv 2009^k \equiv 2^k \equiv 2^1 \equiv 2 \pmod{3}$$
And so we conclude that the exponent is of the form $3k + 2$, or, equivalently, $3k - 1$.

 

[I like Serena]

Problem:
Let $y=x/(1+x)$, where
$$\Large x=\omega^{2009^{2009^{\cdots \text{upto 2009 times}}}}$$
and $\omega$ is a complex root of 1. Then $y$ is

A)$\omega$

B)$-\omega$

C)$\omega^2$

D)$-\omega^2$

Attempt:
I somehow need to show that the huge exponent is of the form $3k$, $3k+1$ or $3k-1$ but I don't see how to do so.

Any help is appreciated. Thanks!

Hi Pranav! ;)

It looks like a case where Fermat's little theorem can be applied repeatedly.
Can you clarify which root of 1 the symbol $\omega$ is?

 

[Saitama]

Hi ILS and Bacterius! :)

Through Euler's Theorem since $\varphi(3) = 2$ (actually the FLT suffices since $3$ is prime) we have:
$$2009^{(2009^l)} \equiv 2009^k \equiv 2^k \equiv 2^1 \equiv 2 \pmod{3}$$

I am lost on this step. How did you apply FLT here?

Can you clarify which root of 1 the symbol $\omega$ is?

The problem statement mentions nothing about that but I think it isn't necessary to solve the problem.

 

[Nono713]

I am lost on this step. How did you apply FLT here?

I am applying the cyclic property of exponents modulo $\varphi(n)$, which follows immediately from Euler's Theorem (or FLT for prime moduli). In other words, for $\gcd(a, n) = 1$. the following holds:
$$x \equiv y \pmod{\varphi(n)} ~ ~ ~ \implies ~ ~ ~ a^x \equiv a^y \pmod{n}$$
In this case, we found that for any integer $l$:
$$2009^l \equiv 1 \pmod{2}$$
And we also know that $2009$ is coprime to $3$, and so we obtain:
$$2009^{2009^l} \equiv 2009^1 \pmod{3}$$
Simplify using $2009 \equiv 2 \pmod{3}$ and the result follows.

 

[Saitama]

I am applying the cyclic property of exponents modulo $\varphi(n)$, which follows immediately from Euler's Theorem (or FLT for prime moduli). In other words, for $\gcd(a, n) = 1$. the following holds:
$$x \equiv y \pmod{\varphi(n)} ~ ~ ~ \implies ~ ~ ~ a^x \equiv a^y \pmod{n}$$
In this case, we found that for any integer $l$:
$$2009^l \equiv 1 \pmod{2}$$
And we also know that $2009$ is coprime to $3$, and so we obtain:
$$2009^{2009^l} \equiv 2009^1 \pmod{3}$$
Simplify using $2009 \equiv 2 \pmod{3}$ and the result follows.

Thanks Bacterius! :)

I have never seen that property before.

But can we proceed from FLT directly without involving the use of Euler's totient function? I have never used it before in problem solving.

From FLT,
$$a^{p-1}\equiv 1\pmod p$$
Here $p=3$, what should be $a$?

 

[Nono713]

Thanks Bacterius! :)

I have never seen that property before.

But can we proceed from FLT directly without involving the use of Euler's totient function? I have never used it before in problem solving.

From FLT,
$$a^{p-1}\equiv 1\pmod p$$
Here $p=3$, what should be $a$?

Sure, you can do it this way. You simply note that $2009^l$ is going to be odd for any $l$, and so it can be written as $m(p - 1) + 1$ for $p = 3$ (so $p - 1 = 2$). Therefore:
$$a^{2009^l} \equiv a^{m(p - 1) + 1} \equiv a^1 \equiv a \pmod{p}$$
Then you put $a = 2009$ as per your problem, and simplify the base modulo $3$, and you're done. Does this make it clearer?

 

[Saitama]

Sure, you can do it this way. You simply note that $2009^l$ is going to be odd for any $l$, and so it can be written as $2(p - 1) + 1$ for $p = 3$ (so $p - 1 = 2$). Therefore:
$$a^{2009^l} \equiv a^{2(p - 1) + 1} \equiv a^1 \equiv a \pmod{p}$$
Then you put $a = 2009$ as per your problem, and simplify the base modulo $3$, and you're done. Does this make it clearer?

I think I see it now but I do not see the reason for writing $2009^l$ in an awkward way i.e $2(p-1)+1$.

Can you please check if the following is correct?

Since $2009^l$ is odd, I write it as $2k+1$, hence,

$$2009^{2009^l}\equiv (2009)^{2k+1} \equiv (2009^k)^2\cdot 2009 \pmod 3$$

From FLT, I can write $(2009^k)^{(3-1)}\equiv 1\pmod 3$ and also, $2009\equiv 2\pmod 3$. Hence,

$$(2009^k)^2\cdot 2009 \equiv 2 \pmod 3$$

EDIT: Woops, that's actually what you did, its just that I did not see it before until I wrote it down myself, thanks Bacterius for all the help! :)

 

[I like Serena]

The problem statement mentions nothing about that but I think it isn't necessary to solve the problem.

Ah, I just noticed that this information is hidden in the title of your thread. (Bandit)
It's the cube root of unity.
So $\omega^3 = 1$.

And I see that is what Bacterius and you have been using all along. (Wasntme)

 

[I like Serena]

Anyway, so now we have that:
$$x= \omega^{3k-1}$$
So which answer should it be? (Wondering)

 

[Saitama]

Anyway, so now we have that:
$$x= \omega^{3k-1}$$
So which answer should it be? (Wondering)

$\omega^{3k-1}$ is same as $\omega^2$. Hence, $y=\omega^2/(1+\omega^2)=\omega^2/(-\omega)=-\omega$ which is the B option. :)