Does a number n exist where 2^n mod 3 = 0?

[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,

 

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

 

[Crisps]

Obviously!

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

Thanks.

 

[Citan Uzuki]

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

 

[graphain]

The MU puzzle from Godel Escher Bach is this problem.

 

[Hepth]

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

(EDIT : 31/2 works? )

 

[Mentallic]

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

 

[CRGreathouse]

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

Still no solutions.

 

[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}.

 

[Hepth]

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

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.

 

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

 

[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?

 

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

 

[xnull]

Ahh, that's very clear.