Difference between revisions of "2007 USAMO Problems/Problem 5"
5849206328x (talk | contribs) m (→See also) |
5849206328x (talk | contribs) (→Solutions) |
||
(One intermediate revision by the same user not shown) | |||
Line 2: | Line 2: | ||
(''Titu Andreescu'') Prove that for every [[nonnegative]] [[integer]] <math>n</math>, the number <math>7^{7^n}+1</math> is the [[product]] of at least <math>2n+3</math> (not necessarily distinct) [[prime]]s. | (''Titu Andreescu'') Prove that for every [[nonnegative]] [[integer]] <math>n</math>, the number <math>7^{7^n}+1</math> is the [[product]] of at least <math>2n+3</math> (not necessarily distinct) [[prime]]s. | ||
− | == | + | ==Solutions== |
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
=== Solution 1 === | === Solution 1 === | ||
− | + | The proof is by induction. The base is provided by the <math>n = 0</math> case, where <math>7^{7^0} + 1 = 7^1 + 1 = 2^3</math>. To prove the inductive step, it suffices to show that if <math>x = 7^{2m - 1}</math> for some positive integer <math>m</math> then <math>(x^7 + 1)/(x + 1)</math> is composite. As a consequence, <math>x^7 + 1</math> has at least two more prime factors than does <math>x + 1</math>. To confirm that <math>(x^7 + 1)/(x + 1)</math> is composite, observe that | |
− | + | <cmath>\begin{align*} | |
− | + | \frac{x^7 + 1}{x + 1} &= \frac{(x + 1)^7 - ((x + 1)^7 - (x^7 + 1))}{x + 1} \\ | |
− | + | &= (x + 1)^6 - \frac{7x(x^5 + 3x^4 + 5x^3 + 5x^2 + 3x + 1)}{x + 1} \\ | |
− | + | &= (x + 1)^6 - 7x(x^4 + 2x^3 + 3x^2 + 2x + 1) \\ | |
− | + | &= (x + 1)^6 - 7^{2m}(x^2 + x + 1)^2 \\ | |
− | + | &= \{(x + 1)^3 - 7^m(x^2 + x + 1)\}\{(x + 1)^3 + 7^m(x^2 + x + 1)\}. | |
− | + | \end{align*}</cmath> | |
− | + | Also each factor exceeds 1. It suffices to check the smaller one; <math>\sqrt{7x}\leq x</math> gives | |
− | + | <cmath>\begin{align*} | |
− | + | (x + 1)^3 - 7^m(x^2 + x + 1) &= (x + 1)^3 - \sqrt{7x}(x^2 + x + 1) \\ | |
− | + | &\geq x^3 + 3x^2 + 3x + 1 - x(x^2 + x + 1) \\ | |
− | + | &= 2x^2 + 2x + 1\geq 113 > 1. | |
− | + | \end{align*}</cmath> | |
− | + | Hence <math>(x^7 + 1)/(x + 1)</math> is composite and the proof is complete. | |
− | < | ||
− | |||
− | |||
− | + | {{alternate solutions}} | |
== See also == | == See also == |
Latest revision as of 09:47, 7 August 2014
Contents
Problem
(Titu Andreescu) Prove that for every nonnegative integer , the number
is the product of at least
(not necessarily distinct) primes.
Solutions
Solution 1
The proof is by induction. The base is provided by the case, where
. To prove the inductive step, it suffices to show that if
for some positive integer
then
is composite. As a consequence,
has at least two more prime factors than does
. To confirm that
is composite, observe that
Also each factor exceeds 1. It suffices to check the smaller one;
gives
Hence
is composite and the proof is complete.
Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.
See also
- <url>viewtopic.php?t=145849 Discussion on AoPS/MathLinks</url>
2007 USAMO (Problems • Resources) | ||
Preceded by Problem 4 |
Followed by Problem 6 | |
1 • 2 • 3 • 4 • 5 • 6 | ||
All USAMO Problems and Solutions |
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.