If $\displaystyle n = 3^{x-1}$, prove $\displaystyle 2^n$ is congruent to -1 (mod $\displaystyle 3^x)$.
I think I should use Euler's Theorem for this but I'm not sure. Thanks for any help!
If $\displaystyle n = 3^{x-1}$, prove $\displaystyle 2^n$ is congruent to -1 (mod $\displaystyle 3^x)$.
I think I should use Euler's Theorem for this but I'm not sure. Thanks for any help!
Oops! Thanks for leading me through this.
So I have $\displaystyle (2^{3^{x -1}})^2} \equiv 1 (mod\ 3^x)$,
which implies that either $\displaystyle (2^{3^{x -1}}) \equiv 1 (mod\ 3^x)$ or $\displaystyle \equiv -1 (mod\ 3^x) $.
But, it can't be 1 because that would mean $\displaystyle (2^{3^{x -1}}) \equiv (2^{3^{x -1}})^2} $? Is that the right reasoning?
This implication isn't correct. It's true that if a prime divides a product of two numbers, then it must divide at least one of them. The same isn't true, however, for prime powers. For example, $\displaystyle 3^2|6 \cdot 15$, but 9 doesn't divide either factor.which implies that either $\displaystyle (2^{3^{x -1}}) \equiv 1 (mod\ 3^x)$ or $\displaystyle \equiv -1 (mod\ 3^x) $.
This point is the crux of the problem. Please think about it. Write out some examples for small values of x. Try to figure out, using the hints already given, why $\displaystyle 3^x$ must divide $\displaystyle (2^{3^{x-1}}) + 1$.
Not quite right, but closer. It's true that $\displaystyle 2 \equiv -1 (mod\ 3)$, but that only implies that $\displaystyle (2^{3^{x -1}})} \equiv -1 (mod\ 3)$, not $\displaystyle (mod\ 3^x)$.
You know that $\displaystyle {3^{x -1}}$ divides the product $\displaystyle ((2^{3^{x -1}})} +1)((2^{3^{x-1}}) - 1)$. Can you prove that 3 does not divide the second factor? If so, do you see why that solves the problem?