Prove that
where (and are different factors of the number ).
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 .
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.
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.
Does this induction prove that the results are composite numbers??