Clan x86

General Forums => Academic / School => Math and Other Problems => Topic started by: Ender on October 23, 2006, 08:18:47 pm

Title: [Solved] The Toothfairy Problem
Post by: Ender on October 23, 2006, 08:18:47 pm: Show that 7^n - 1 is divisible by 6 for any positive integer n.

I'll post the solution on Wednesday.
Title: Re: The Toothfairy Problem
Post by: Rule on October 23, 2006, 09:47:43 pm: Simple induction... is this a homework assignment question?
Title: Re: The Toothfairy Problem
Post by: Sidoh on October 24, 2006, 12:24:43 am: (http://latex.sidoh.org/?render64=JCQgJFxcKg0KXGxlZnQoN15uLTFccmlnaHQpXG1vZHs2fT0wIFxcDQo3Xm5cZXF1aXYgMVxsZWZ0KFxtb2R7Nn1ccmlnaHQpIFxcDQooN14xLTE9NilcZXF1aXYgMChcbW9kezZ9KSQNCg0KJFxcJEFzc3VtZTogJDdeay0xXGVxdWl2IDAoXG1vZHs2fSlcXA0KN157aysxfS0xPTdcbGVmdCg3XmstMSkrNiQNCg0KJFxcXFwkU2luY2UgJDdeay0xIFxlcXVpdiAwKFxtb2R7Nn0pJCBpcyB0cnVlIGJ5IHRoZSBpbmR1Y3Rpb24gaHlwb3RoZXNpcyBhbmQgNiBpcyBkaXZpc2libGUgYnkgNiwgdGhlIHdob2xlIHN0YXRlbWVudCAkN15uLTEgXGVxdWl2IDAoXG1vZHs2fSkkIGlzIHRydWUu)
Title: Re: The Toothfairy Problem
Post by: Rule on October 24, 2006, 04:58:55 pm: Quote from: Sidoh on October 24, 2006, 12:24:43 am
(http://latex.sidoh.org/?render64=JCQgJFxcKg0KXGxlZnQoN15uLTFccmlnaHQpXG1vZHs2fT0wIFxcDQo3Xm5cZXF1aXYgMVxsZWZ0KFxtb2R7Nn1ccmlnaHQpIFxcDQooN14xLTE9NilcZXF1aXYgMChcbW9kezZ9KSQNCg0KJFxcJEFzc3VtZTogJDdeay0xXGVxdWl2IDAoXG1vZHs2fSlcXA0KN157aysxfS0xPTdcbGVmdCg3XmstMSkrNiQNCg0KJFxcXFwkU2luY2UgJDdeay0xIFxlcXVpdiAwKFxtb2R7Nn0pJCBpcyB0cnVlIGJ5IHRoZSBpbmR1Y3Rpb24gaHlwb3RoZXNpcyBhbmQgNiBpcyBkaXZpc2libGUgYnkgNiwgdGhlIHdob2xlIHN0YXRlbWVudCAkN15uLTEgXGVxdWl2IDAoXG1vZHs2fSkkIGlzIHRydWUu)
You need to specify that you are assuming 7^k-1 is divisible by 6 for some k>=1, then you have shown the formula holds for all n>=1.

A picky detail, but one that is notable in rigorous math courses.
Title: Re: The Toothfairy Problem
Post by: rabbit on October 24, 2006, 05:06:10 pm: (http://latex.sidoh.org/?render=6%20%7C%20%287%5Ek%20-1%29)
(http://latex.sidoh.org/?render=%286%20%2B%201%29%20%7C%207%5Ek)
(http://latex.sidoh.org/?render=7%20%7C%207%5Ek)

Done.
Title: Re: The Toothfairy Problem
Post by: Sidoh on October 24, 2006, 05:30:35 pm: Quote from: Rule on October 24, 2006, 04:58:55 pm
You need to specify that you are assuming 7^k-1 is divisible by 6 for some k>=1, then you have shown the formula holds for all n>=1.

A picky detail, but one that is notable in rigorous math courses.

Oops, yeah. I should have said "Assume 7^k-1 is divisible by 6 for some arbitrary integer greater than one, k," right?
Title: Re: The Toothfairy Problem
Post by: Ender on October 29, 2006, 09:15:49 pm: Another way to do this, which does not require knowledge of modular arithmetic or number theory, is using the polynomial combinatorics whatever theorem:

(http://latex.sidoh.org/?render=7%5E%7Bn%7D%20%3D%20%286%20%2B%201%29%5E%7Bn%7D%20-%201%0D%0A%0D%0A%3D%20%5Cleft%28%5Cbegin%7Barray%7D%7Bcc%7Dn%20%5C%5C%200%5Cend%7Barray%7D%5Cright%29%206%5E%7Bn%7D1%5E%7B0%7D%20%5Ctimes%20%5Cleft%28%5Cbegin%7Barray%7D%7Bcc%7Dn%20%5C%5C%201%5Cend%7Barray%7D%5Cright%29%206%5E%7Bn-1%7D1%5E%7B1%7D%20%5Ctimes%20...%20%5Ctimes%20%5Cleft%28%5Cbegin%7Barray%7D%7Bcc%7Dn%20%5C%5C%20n%5Cend%7Barray%7D%5Cright%29%206%5E%7B0%7D1%5E%7Bn%7D%20-%201%0D%0A%0D%0A%0D%0A%0D%0A)
Title: Re: The Toothfairy Problem
Post by: rabbit on October 29, 2006, 09:42:23 pm: While that may not require knowledge of modular arithmetic and number theory, it does require either (A) set theory (I think) or (B) basic discrete concepts.
Title: Re: The Toothfairy Problem
Post by: Ender on October 31, 2006, 08:29:45 pm: 2 + 2 requires knowledge of set theory =p

but yeah it requires knowledge of basic combinatorics
Title: Re: The Toothfairy Problem
Post by: rabbit on November 01, 2006, 04:34:03 pm: Which is Discrete, vis a vis same level as NT :P
Title: Re: The Toothfairy Problem
Post by: Ender on November 01, 2006, 07:36:26 pm: Discrete math is much more common to high school math curricula* than number theory is, but yeah, there's no restriction to what math you can use in these problems.

* Grammar Policed on behalf of Sidoh's (pedantic) request
Title: Re: The Toothfairy Problem
Post by: Sidoh on November 01, 2006, 07:48:19 pm: Quote from: Ender on November 01, 2006, 07:36:26 pm
curriculae

You made that word up. :P
Title: Re: The Toothfairy Problem
Post by: rabbit on November 01, 2006, 08:55:53 pm: Quote from: Ender on November 01, 2006, 07:36:26 pm
Discrete math is much more common to high school math curricula* than number theory is, but yeah, there's no restriction to what math you can use in these problems.

* Grammar Policed on behalf of Sidoh's (pedantic) request
Hmmm....that means I can use my made up math!
Title: Re: The Toothfairy Problem
Post by: Sidoh on November 01, 2006, 09:23:04 pm: Quote from: Ender on November 01, 2006, 07:36:26 pm
* Grammar Policed on behalf of Sidoh's (pedantic) request

If it's truely pedantic, why did you go through the effort of fixing it?
Title: Re: The Toothfairy Problem
Post by: Ender on November 01, 2006, 09:40:42 pm: I just wanted to use the word pedantic because I rarely get to use it and it's really fun to say.
Title: Re: The Toothfairy Problem
Post by: Sidoh on November 01, 2006, 09:43:51 pm: Quote from: Ender on November 01, 2006, 09:40:42 pm
I just wanted to use the word pedantic because I rarely get to use it and it's really fun to say.

That was one of the predictions I'd made to my own question. :P