Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

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

  1. Feb 8, 2009 #1
    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

  2. jcsd
  3. Feb 8, 2009 #2
    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.
  4. Feb 8, 2009 #3

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

  5. Feb 8, 2009 #4
    Just out of curiosity, what is the puzzle you are trying to solve?
  6. May 20, 2009 #5
    The MU puzzle from Godel Escher Bach is this problem.
  7. May 21, 2009 #6


    User Avatar
    Gold Member

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

    (EDIT : 31/2 works? )
    Last edited: May 21, 2009
  8. May 21, 2009 #7


    User Avatar
    Homework Helper

    Using n=31/2 leaves an irrational, and that is not divisible by the rational number 3.
  9. May 21, 2009 #8


    User Avatar
    Science Advisor
    Homework Helper

    Still no solutions.
  10. May 21, 2009 #9
    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}.
  11. May 22, 2009 #10


    User Avatar
    Gold Member

    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.
  12. May 22, 2009 #11

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    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.
  13. May 22, 2009 #12
    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?
  14. May 24, 2009 #13
    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.
  15. May 24, 2009 #14
    Ahh, that's very clear.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook