Prove that

where (and are different factors of the number ).

Printable View

- Jan 29th 2008, 03:59 AMjames_bondFactors of n!
Prove that

where (and are different factors of the number ). - Jan 29th 2008, 04:37 AMmr fantastic
- Jan 29th 2008, 04:40 AMjames_bond
- Jan 29th 2008, 08:07 PMThePerfectHacker
This is a proof outline. The proof is on induction on the factorial. It is clearly true for small numbers. We will prove it is true for . Let . If then by induction there exists distinct so that . Thus, it is safe to assume that . The goal is to find a factor(s) of such that then by induction where are distinct and thus clearly and thus it is distinct too. Which means .

- Jan 30th 2008, 05:28 AMOpalg
Proof by induction on n: the result is true for n=2. Suppose it holds for n, and let . Divide x by n+1, getting a quotient q and a remainder r, so that , where and . (Note that this is slightly different from the normal convention. I want the remainder to lie in the range 1 to n+1, rather than 0 to n.)

By the inductive hypothesis, , where the numbers c_j are distinct divisors of n!. Then . Define and . These numbers are all distinct (because and all the other numbers are greater than n+1), and they are all divisors of (n+1)!.

That completes the inductive step, so the result is proved. - Jan 30th 2008, 08:12 AMThePerfectHacker
- Jun 4th 2008, 01:58 PMduggaboya little confused
Proof by induction on n: the result is true for n=2. Suppose it holds for n, and let http://www.mathhelpforum.com/math-he...d1058765-1.gif. Divide x by n+1, getting a quotient q and a remainder r, so that http://www.mathhelpforum.com/math-he...f396952f-1.gif, where http://www.mathhelpforum.com/math-he...82df4850-1.gif and http://www.mathhelpforum.com/math-he...7dd9157d-1.gif. (Note that this is slightly different from the normal convention. I want the remainder to lie in the range 1 to n+1, rather than 0 to n.)

By the inductive hypothesis, http://www.mathhelpforum.com/math-he...c5461872-1.gif, where the numbers c_j are distinct divisors of n!. Then http://www.mathhelpforum.com/math-he...0e70e550-1.gif. Define http://www.mathhelpforum.com/math-he...2b8e8394-1.gif and http://www.mathhelpforum.com/math-he...fa653b07-1.gif. These numbers are all distinct (because http://www.mathhelpforum.com/math-he...fce1bbaa-1.gif and all the other numbers are greater than n+1), and they are all divisors of (n+1)!.

That completes the inductive step, so the result is proved.

Does this induction prove that the results are composite numbers?? - Jun 5th 2008, 01:14 AMOpalg