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

  • Context: High School 
  • Thread starter Thread starter Crisps
  • Start date Start date
Click For Summary

Discussion Overview

The discussion revolves around the question of whether there exists a number n such that 2^n mod 3 equals 0. Participants explore this mathematical concept, examining both integer and rational values for n, and discussing implications related to prime factorization.

Discussion Character

  • Exploratory
  • Mathematical reasoning
  • Debate/contested

Main Points Raised

  • One participant expresses confusion about finding an n such that 2^n mod 3 = 0, noting attempts with the first 64 integers.
  • Another participant argues that 2^n cannot be divisible by 3 due to the uniqueness of prime factorizations, suggesting that no solution exists.
  • A participant mentions the MU puzzle from "Gödel, Escher, Bach" as the context for their inquiry.
  • Some participants propose considering n as a rational number, with one suggesting that n = 31/2 might work, but later discussions clarify that this does not yield a valid solution.
  • A participant attempts a formal proof by induction to show that no natural number x satisfies 2^x mod 3 = 0, but another questions the necessity of induction in this case.
  • There is a clarification that 2^n already represents its prime factorization, and since it contains no factor of 3, it cannot be divisible by 3.

Areas of Agreement / Disagreement

Participants generally agree that there is no integer n such that 2^n mod 3 = 0, but there is some disagreement regarding the exploration of rational numbers and the validity of the formal proof presented.

Contextual Notes

The discussion includes limitations related to the assumptions about n being an integer or rational number, and the implications of prime factorization in the context of modular arithmetic.

Crisps
Messages
2
Reaction score
0
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,
 
Physics news on Phys.org
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.
 
Obviously!

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

Thanks.
 
Just out of curiosity, what is the puzzle you are trying to solve?
 
The MU puzzle from Godel Escher Bach is this problem.
 
What if "n" doesn't necessarily mean an integer, but rather a rational number.

(EDIT : 31/2 works? )
 
Last edited:
Using n=31/2 leaves an irrational, and that is not divisible by the rational number 3.
 
Hepth said:
What if "n" doesn't necessarily mean an integer, but rather a rational number.

Still no solutions.
 
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
Mentallic said:
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.
 
  • #11
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
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
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
Ahh, that's very clear.
 

Similar threads

For n>3, show that the integers n, n+2, n+4 cannot all be prime
  • · Replies 27 ·
Replies
27
Views
4K
Undergrad Dfns group action & group, written in terms of the other
  • · Replies 26 ·
Replies
26
Views
1K
Undergrad Proving inequality about dimension of quotient vector spaces
  • · Replies 25 ·
Replies
25
Views
4K
Graduate Anti-dual numbers and what are their properties?
  • · Replies 1 ·
Replies
1
Views
2K
Graduate When n*(n+1)/2 - k is never a square
  • · Replies 2 ·
Replies
2
Views
2K
Graduate How Does U(1) Double-Cover SO(2) for a Specified Angle?
  • · Replies 2 ·
Replies
2
Views
2K
Graduate Number of quadratic residues mod N>1
  • · Replies 3 ·
Replies
3
Views
4K
High School What Is the Largest Natural Number $n$ Such That $2^n$ Divides $3^{2016}-1$?
  • · Replies 1 ·
Replies
1
Views
2K
Graduate About a natural extension of Collatz conjecture
  • · Replies 3 ·
Replies
3
Views
1K
Undergrad Congruence Subgroups and Modular Forms Concept Questions
  • · Replies 1 ·
Replies
1
Views
2K