Math Challange!

[Mathochist]

Ok, this may not belong here, but heck with all that. Here's a fun proof I did the other day since I was bored and it was too hot out to shred:

Prove that no power of 2 divides 3, i.e. (2 to the nth power)/3 is never a whole number, no matter what value you choose for n.

Now the fun part of this for me was that I got to use induction and contradiction all in one proof, although now that I think about it, a pretty swift and strong argument can be made using modular congruance. I'm just not sure to what extent that argument would constitute a valid mathematical proof.

Anyways, thoughts?

[Colin]

2^n is a prime factorization, and is therefore unique. Since 3 isn't in there, it doesn't divide 2^n. Hardly any need for induction there!

[max]

good point.

[Jeremy]

I'd like to see the real proof. It's too long since I've done maths to figure it out for myself - and even if I could, the thing I hated most about maths was writing out how I figured out the answers (I once got a C on a maths test even though I got every answer right because I didn't show any working out )

[max]

What Newf wrote is very "real" and crystal clear. It also has the advantage of being very concice.

[wolfpac444]

If you want to use modular congruence, the easiest way would go something like this:

Let n be a nonnegative integer. Then, we can write either n=2k or n=2k+1 for some nonnegative integer k. Suppose n=2k. Then,

Code: Select all

2^n = 2^(2k) = 4^k == 1^k == 1 (mod 3).

Thus, 3 does not divide 2^n in this case.

Now, let us assume n=2k+1. We then have

Code: Select all

 2^n = 2^(2k+1) = 2*4^k ==2*1^k == 2 (mod 3).

Therefore, we have that 3 does not divide 2^n in this case, and furthermore, 3 does not divide 2^n in general.

[Note: == represents congruence in the above proof.]

[Colin]

I'd like to see the real proof.

Don't be frontin' on my proof, yo.

[Jeremy]

The real proof as in the proof that Rob was looking for. I'm sorry if I offended you and that I didn't make that clear. I think you probably knew what I was talking about.

Good proofs are like poetry. Your proof was like a tax law clause.

[Mathochist]

Sorry gang, I've been without internet for a bit.

I have to admit that Newf's proof kicks the mathematical tar off of mine for all the reasons Max mentioned. That just shows how keen I am to overanalyze anything. I guess next time I should consider invoking the fundamental theorem of arithmetic a smart idea in a proof about factors.

However, since you asked, Jeremy, I'm all too glad to submit my obfuscating proof:

1. Step one of induction is to show the theorem true for a particular n, usually 0 or 1. Either is easy here; 2^0=1 which doesn't divide 3, and 2^1=2, which also doesn't divide 3.

2. Step two of induction has me choose some unspecified but particular 'k' and assume 2^k doesn't divide 3.

3. Now I fire up my contradiction engines and assume that 2^(k+1) DOES divide 3.

4. Now things can get moving. The assumption that 2^(k+1) divides 3 is to say that 2^(k+1)=3p for some natural number p. Also 2^(k+1)=2*2^k, since that's how exponents work.
Meaning: 2*2^k=3p

5. There are two possibilities for p.
5.1 If p is even, then we can divide both sides of the equation by 2:
2^k=3(p/2), which means 2^k equals 3 times some number, which means 2^k divides 3, which contradicts the assumption in step 2.
5.2 If p is odd, then 3p is odd, and since that equals 2*2^k, 2*2^k must be odd too, which is also a contradiction.

6. Since the assumption in step 3 yields a contradiction (no matter how you slice p), that assumption is false, i.e. 2^(k+1) does not divide 3.

7. Since the assumption in step 2 yielded the result in step 6 (i.e. If 2^k doesn't divide 3, then neither does 2^(k+1).), the assertion is true for all natural numbers.

8. So 2^n doesn't divide 3, for all natural numbers n. QED

[HG]

"Mike talks about math and makes it sound like literature"


-Ted

[Colin]

Hey Rob, a real minor note here, but in your first post you asked whether some 2^n divides 3, where you really meant to ask whether 3 divides some 2^n. I didn't mention it, but you had the same mixup in your latest post. Keep those contradiction engines firing, they'll serve you well.

Math is sometimes fun.

[footjam_heger]

oh rob likes difficult maths!
i will you challenge with german!

[comastalker]

I like induction...
you're able to proof that it is possible to pack an infinite amount of socks into a case