# Does (2^n) mod 3 = 0 exist?

1. Feb 8, 2009

### Crisps

This seems a simple question but I am unsure as to why I cannot find a number n where

2^n mod 3 = 0

I am trying to solve a puzzle (I'm not a student) and I think that this may be the key to the puzzle. At first it seemed pretty plausible that there would be a 2^n which was divisible by 3 but having tried the first 64 n's it is now seeming that there may not be. I cannot understand why though. Can anybody let me know if this number exists and if not why not?

(In case you need an example)

2^2 = 4, 4mod3 = 1
2^3 = 8, 8mod3 = 2
etc

Thanks,

2. Feb 8, 2009

### Citan Uzuki

Well remember that if 2^n ≡ 0 mod 3, then 3 must divide 2^n. But by uniqueness of prime factorizations, 3 cannot divide 2^n for any n. That is why the equation you gave above has no solution.

3. Feb 8, 2009

### Crisps

Obviously!

I'll have to try and think of another solution to the puzzle.

Thanks.

4. Feb 8, 2009

### Citan Uzuki

Just out of curiosity, what is the puzzle you are trying to solve?

5. May 20, 2009

### graphain

The MU puzzle from Godel Escher Bach is this problem.

6. May 21, 2009

### Hepth

What if "n" doesn't necessarily mean an integer, but rather a rational number.

(EDIT : 31/2 works? )

Last edited: May 21, 2009
7. May 21, 2009

### Mentallic

Using n=31/2 leaves an irrational, and that is not divisible by the rational number 3.

8. May 21, 2009

### CRGreathouse

Still no solutions.

9. May 21, 2009

### xnull

My attempt at a formal proof by induction.

For a number x in the set of natural numbers, prove that there is no value for x such that 2^x mod 3 = 0.

For some number n mod 3 to be equal to 0, 3 must be a number in n's prime factorization.

Assume that 2^x mod 3 != 0.
2^x has a prime factorization Z.
2^(x+1) has a prime factorization Z U {2}.
Therefore 2^(x+1) mod 3 != 0.

For x = 0...
2^x mod 3 = 1.
The prime factorization of 2^x is {1}.

10. May 22, 2009

### Hepth

Yeah I think mathematica was just set to a low accuracy when i did it. Doesnt make sense that any 2^(x/2) would be rational.

11. May 22, 2009

### matt grime

Your formal proof, xnull assumes uniqueness of prime factorization - if you assume that the there is nothing else left to prove, so no need to induct on n or anything at all.

12. May 22, 2009

### xnull

matt grime, I am eager to understand why my attempt at a formal proof is invalid.

I'm not certain from your post what I have done wrong. Could you explain it again?

13. May 24, 2009

### Moo Of Doom

He's not saying the proof is invalid, just that it uses induction where it is unnecessary.

2^n is already the prime factorization of 2^n. Since there is no factor of 3 there, 3 can't divide it.

14. May 24, 2009

### xnull

Ahh, that's very clear.