1. ## Euler's theorem problem

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!

2. Originally Posted by Arzx
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!
Euler's Theorem states that if (a,m) = 1, then

$\displaystyle a^{\phi(m)} \equiv 1 (mod\ m)$

What do you get if you plug in a = 2 and m = $\displaystyle 3^x$? Can you use that congruence to solve the problem?

3. Originally Posted by Petek
Euler's Theorem states that if (a,m) = 1, then

$\displaystyle a^{\phi(m)} \equiv 1 (mod\ m)$

What do you get if you plug in a = 2 and m = $\displaystyle 3^x$? Can you use that congruence to solve the problem?
If I plug in those values, I get that $\displaystyle 2^{3^{x} -1} \equiv 1 (mod\ 3^x)$, (I think). But it needs to be congruent to negative 1, so I'm not sure how to fix that. I know congruence-wise -1 is the same as $\displaystyle 3^x -1$ but that doesn't help does it?

4. Originally Posted by Arzx
If I plug in those values, I get that $\displaystyle 2^{3^{x} -1} \equiv 1 (mod\ 3^x)$, (I think). But it needs to be congruent to negative 1, so I'm not sure how to fix that. I know congruence-wise -1 is the same as $\displaystyle 3^x -1$ but that doesn't help does it?
Take another look at your congruence. If p is a prime and k is a positive integer, then

$\displaystyle \phi(p^k) = (p - 1)p^{k-1}$

5. Originally Posted by Petek
Take another look at your congruence. If p is a prime and k is a positive integer, then

$\displaystyle \phi(p^k) = (p - 1)p^{k-1}$
Yikes, ok, so then I get that $\displaystyle (2^2)(2^{3^{x -1}}) \equiv 1 (mod\ 3^x)$? Where do I go from there?

6. Originally Posted by Arzx
Yikes, ok, so then I get that $\displaystyle (2^2)(2^{3^{x -1}}) \equiv 1 (mod\ 3^x)$? Where do I go from there?
You made a simple algebra error with exponents. Your congruence should be

$\displaystyle (2^{2\cdot 3^{x -1}}) \equiv 1 (mod\ 3^x)$

Write this as

$\displaystyle (2^{3^{x -1}})^2} \equiv 1 (mod\ 3^x)$

and go from there.

7. Originally Posted by Petek
You made a simple algebra error with exponents. Your congruence should be

$\displaystyle (2^{2\cdot 3^{x -1}}) \equiv 1 (mod\ 3^x)$

Write this as

$\displaystyle (2^{3^{x -1}})^2} \equiv 1 (mod\ 3^x)$

and go from there.
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?

8. Signing off for the day. Will reply tomorrow. You're getting close!

9. Originally Posted by Arzx
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)$
From here, I'm still not solid on why it must be -1 and not 1. I don't think saying $\displaystyle (2^{3^{x -1}}) \equiv (2^{3^{x -1}})^2}$ is really the correct idea, but I don't know what it is.

10. which implies that either $\displaystyle (2^{3^{x -1}}) \equiv 1 (mod\ 3^x)$ or $\displaystyle \equiv -1 (mod\ 3^x)$.
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.

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$.

11. Originally Posted by Petek
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.

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$.
Hmmm...OK.
If x=1, then $\displaystyle 3^1$ does divide $\displaystyle (2^{1}) + 1$ (3/3)
If x =2, then $\displaystyle 3^2$ does divide $\displaystyle (2^{3}) + 1$ (9/9)

Is the reason because 2 $\displaystyle \equiv -1 (mod\ 3)$? Sorry, I'm still not sure what to do.

12. 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?

13. Originally Posted by Petek
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?

Too many laps on the same circuit: $\displaystyle 2^{2n-1}=2\!\!\pmod 3\,\,\,\forall n\in\mathbb{N}$

Tonio

14. Originally Posted by tonio
Too many laps on the same circuit: $\displaystyle 2^{2n-1}=2\!\!\pmod 3\,\,\,\forall n\in\mathbb{N}$

Tonio
I'm glad to see that you know how to solve the problem, but I was trying to help the OP figure this out on his own.

15. Oh, I see!! Thanks both of you

Page 1 of 2 12 Last