Difference between revisions of "2002 IMO Shortlist Problems/N3"

Latest revision as of 05:38, 12 November 2019

Problem

Let $p_{1}, p_{2}, \ldots , p_{n}$ be distinct primes greater than 3. Show that $2^{p_{1}p_{2} \cdots p_{n}} + 1$ has at least $4^n$ divisors.

Solutions

Solution 1

Lemma 1. If $k > m$ , then $km$ has at least twice as many divisors as $m$ .

Proof. For every divisor $a$ of $m$ , $ka$ is clearly a divisor of $km$ , but not $m$ .

Lemma 2. If $u$ and $v$ are relatively prime odd numbers, then the greatest common factor of $2^u + 1$ and $2^v + 1$ is 3.

Proof. Clearly, 3 divides both $2^u + 1$ and $2^v + 1$ . Now, suppose that there is some $t > 3$ which divides both $2^u + 1$ and $2^v + 1$ . Then $2^u \equiv 2^v \equiv -1 \pmod{t}$ . But this means that both $u$ and $v$ are divisible by half the order of 2 in mod $t$ , contradicting our assumption that $u$ and $v$ are relatively prime.

We now note that since

$2^{uv} = (2^{u} + 1) \left[ \sum_{i=0}^{v-1} (-2)^{ui} \right] \qquad \qquad$ ,

we know that $2^{uv} + 1$ is divisible by $2^u + 1$ , and, by symmetry, $2^v$ also, and therefore also by $(2^u + 1)(2^v +1)/3$ .

We now prove the result by induction on $n$ . Our base case, $n=1$ , is easy, since we know that $2^{p_1} + 1$ is divisible by 3, and is greater than 27. Now, set $u = p_{1}\cdots p_{n-1}$ and $v = p_n$ . By Lemma 2, we know that $2^{u} + 1$ and $2^{v} + 1$ are relatively prime; hence $(2^u +1)(2^v + 1)/3$ has at least $2 \cdot 4^{n-1}$ factors, by the inductive hypothesis.

We know that $(2^u +1)(2^v + 1)/3$ divides $2^{uv} + 1$ . We also know that $uv > 2(u+v)$ , whence $2^{uv} > \left[ (2^u + 1)(2^v + 1)/3 \right]^2$ . Then by Lemma 1,

$d(2^{uv} + 1) \ge d \left[ (2^{u}+1)(2^{v}+1)/3 \right] \ge 4^{n}$ .

Q.E.D.

Solution 2

We proceed by induction. For our base case, $n = 1$ , we note that $2^{p_1} +1$ is divisible by 3. Since $p_1 \ge 5$ , $2^{p_1} +1$ is clearly greater than 3 and cannot be a larger power of three, since this would require $p_1 \equiv 3 \pmod{6}$ . Therefore $2^{p_1} + 1$ has some other prime factor and therefore at least 4 factors overall.

Now, suppose the proposition holds for $n = k-1$ . Without loss of generality, let $p_{k}$ be the minimum of $p_{1}, \ldots , p_{k}$ . We shall abbreviate $q = \prod_{i=1}^{k-1}p_i$ . We note the relation

$2^{qp_k} + 1 = \left( 2^q + 1 \right) \left[ \sum_{i=0}^{p_{k}-1} (-2)^{qi} \right]$ .

Since $2^q + 1$ has at least $4^{k-1}$ factors, it will suffice to show that $\sum_{i=0}^{p_{k}-1} (-2)^{qi}$ is relatively prime to $2^q + 1$ , and has at least four factors.

We note that in general, $\sum_{i=0}^{p_{k}-1}(-x)^{i}$ has remainder $p_k$ when divided by $x+1$ . But $p_k$ cannot divide $2^q + 1$ , as this would require $2^q \equiv -1 \pmod{p_k-1}$ when $q$ is relatively prime to $p_k - 1$ . Hence $\sum_{i=0}^{p_{k}-1} (-2)^{qi}$ and $2^q + 1$ are relatively prime.

We now claim that $\sum_{i=0}^{p_{k}-1}(-2)^{qi}$ has at least four factors. We start by noting that in general, $\sum_{i=0}^{p_{k}-1} x^i$ divides $\sum_{i=0}^{p_{k}-1} x^{qi}$ , since the roots of the former are the nonreal $p_{k}$ th roots of unity and $q \perp p_{k}$ .

Since clearly $\sum_{i=0}^{p_{k}-1} (-2)^{qi} > \sum_{i=0}^{p_{k}-1} (-2)^i$ , it is sufficient to show that the former is not the square of the latter (i.e., that the former is either a higher power of the latter, or some other prime divides the latter, either of which implies that the former has at least four factors). But this follows from

$\begin{matrix} \sum_{i=0}^{p_{k}-1} (-2)^{qi} & > & 2^{q(p_{k}-1) - 1} \quad \\ & > & \left( 2^{p_{k}} \right)^2 \qquad \quad \\ & > &\left[ \sum_{i=0}^{p_{k}-1} (-2)^i \right]^2 \end{matrix}$

Thus $\sum_{i=0}^{p_{k}-1} (-2)^{qi}$ has at least four factors and is relatively prime to $2^{q} + 1$ , completing the induction.

Solution 3

We proceed by induction. Base case $n=1$ . Observe that $3|2^{p_1}+1$ , and since $p_1>3$ , $2^{p_1}+1>9 \implies \frac{2^{p_{1}}+1}{3}>3$ so $2^{p_1}+1$ has at least 4 divisors.

Now suppose the proposition holds for $n=h$ .

lemma 1: if $gcd(a,b)=1$ with $a$ and $b$ both being odd, then $gcd(2^a+1,2^b+1)=3$ .

Proof: let p be a prime that divides both $2^a+1$ and $2^b+1$ . Then p divides both $2^{2a}-1$ and $2^{2b}-1$ . Since $2^{2a}\equiv 1$ (mod $p$ ) and $2^{2b}\equiv 1$ (mod $p$ ), $ord_{p}\left(2\right)$ divides $2a$ and $2b$ . But, $gcd(a,b)=1$ , so $ord_{p}\left(2\right)=2 \implies p=3$ . Hence proven.

lemma 2: $3||2^p+1$ , with $p$ being a prime greater than $3$ .

Proof; It suffices to show that $9\nmid 2^p+1$ . for $0\le i\le8$ , the only solution to $2^i+1\equiv 0$ (mod $9$ ) is $i=3$ . $6$ is the smallest natural $k$ such that $2^k-1\equiv 0$ (mod $9$ ). This means that if $2^m+1\equiv 0$ (mod $9$ ), $m\equiv 3$ (mod $6$ ), but $p$ is a prime greater than $3$ , so this is not possible.

Note that $\gcd\left(2^{p_{1}p_{2}\cdot\cdot\cdot p_{n}}+1,\ 2^{p_{n+1}}+1\right)=3$ . Let $m=\frac{2^{p_{n+1}}+1}{3}$ . Note that $\left(2^{p_{1}p_{2}\cdot\cdot\cdot p_{n}}+1\right)\left(2^{p_{n+1}}+1\right)<3\left(2^{p_{1}p_{2}\cdot\cdot\cdot p_{n}p_{n+1}}+1\right) \implies \left(2^{p_{1}p_{2}\cdot\cdot\cdot p_{n}}+1\right)m<\left(2^{p_{1}p_{2}\cdot\cdot\cdot p_{n}p_{n+1}}+1\right)$ . So $2^{p_{1}p_{2}\cdot\cdot\cdot p_{n}p_{n+1}}+1=\left(2^{p_{1}p_{2}\cdot\cdot\cdot p_{n}}+1\right)mx$ . Note that $gcd(m,2^{p_{1}p_{2}\cdot\cdot\cdot p_{n}}+1)=1$ .

I will now prove $x>2^{p_{1}p_{2}\cdot\cdot\cdot p_{n}}+1$ . Note that $x=\frac{3\left(2^{p_{1}p_{2}\cdot\cdot\cdot p_{n}p_{n+1}}+1\right)}{\left(2^{p_{1}p_{2}\cdot\cdot\cdot p_{n}}+1\right)\left(2^{p_{n+1}}+1\right)}$ . We wish to prove $x=\frac{3\left(2^{p_{1}p_{2}\cdot\cdot\cdot p_{n}p_{n+1}}+1\right)}{\left(2^{p_{1}p_{2}\cdot\cdot\cdot p_{n}}+1\right)\left(2^{p_{n+1}}+1\right)}>2^{p_{1}p_{2}\cdot\cdot\cdot p_{n}}+1$ . Rearrange the inequality to get $\left(2+1\right)\left(2^{p_{1}p_{2}\cdot\cdot\cdot p_{n}p_{n+1}}+1\right)>\left(2^{p_{1}p_{2}\cdot\cdot\cdot p_{n}}+1\right)^{2}\left(2^{p_{n+1}}+1\right)$ . Note that $p_{1}p_{2}\cdot\cdot\cdot p_{n}p_{n+1}+1>2p_{1}p_{2}\cdot\cdot\cdot p_{n}+p_{n+1}$ , which implies the inequality. Since $x>2^{p_{1}p_{2}\cdot\cdot\cdot p_{n}}+1$ , $x\nmid 2^{p_{1}p_{2}\cdot\cdot\cdot p_{n}}+1$ .

Also, note that $2^{p_{1}p_{2}\cdot\cdot\cdot p_{n}}+1>m \implies x>m$ . This means $mx$ has at least four factors. Note that if $gcd(x,2^{p_{1}p_{2}\cdot\cdot\cdot p_{n}}+1)=1$ , $mx$ would be relatively prime to $2^{p_{1}p_{2}\cdot\cdot\cdot p_{n}}+1$ , which would mean $2^{p_{1}p_{2}\cdot\cdot\cdot p_{n}p_{n+1}}+1$ has at least $4\cdot4^{h}=4^{h+1}$ factors.

Assume $x$ and $m$ are not relatively prime. Then there exists some prime $q$ such that $v_{q}\left(x\right)>v_{q}\left(2^{p_{1}p_{2}\cdot\cdot\cdot p_{n}}+1\right)$ . Let $2^{p_{1}p_{2}\cdot\cdot\cdot p_{n}p_{n+1}}+1=q_{1}^{e_{1}}q_{2}^{e_{2}}\cdot\cdot\cdot q_{k}^{e_{k}}$ , $m=pD$ and $x=kq_{1}^{e_{1}+f}$ , with $q_1$ being the prime in question. Note that $f\ge1$ . ( $p$ is relatively prime to $2^{p_{1}p_{2}\cdot\cdot\cdot p_{n}}+1$ ). Then $2^{p_{1}p_{2}\cdot\cdot\cdot p_{n}p_{n+1}}+1=q_{1}^{2e_{1}+f}q_{2}^{e_{2}}\cdot\cdot\cdot q_{k}^{e_{k}}p\cdot D\cdot k$ . Let $d(n)$ be the number of divisors of $n$ . Then $d\left(q_{1}^{2e_{1}+f}q_{2}^{e_{2}}\cdot\cdot\cdot q_{k}^{e_{k}}p\cdot D\cdot k\right)\ge d\left(q_{1}^{2e_{1}+f}q_{2}^{e_{2}}\cdot\cdot\cdot q_{k}^{e_{k}}p\right)=\left(2e_{1}+f+1\right)\left(e_{2}+1\right)\cdot\cdot\cdot\left(e_{k}+1\right)\cdot2$ . Note that $f+1\ge 2$ , so $2e_{1}+f+1\ge2\left(e_{1}+1\right) \implies \left(2e_{1}+f+1\right)\left(e_{2}+1\right)\cdot\cdot\cdot\left(e_{k}+1\right)\cdot2\ge4\left(e_{1}+1\right)\left(e_{2}+1\right)\cdot\cdot\cdot\left(e_{k}+1\right)$ . From the inductive step $d(2^{p_{1}p_{2}\cdot\cdot\cdot p_{n}}+1)=\left(e_{1}+1\right)\left(e_{2}+1\right)\cdot\cdot\cdot\left(e_{k}+1\right)\ge 4^h$ , so $4\left(e_{1}+1\right)\left(e_{2}+1\right)\cdot\cdot\cdot\left(e_{k}+1\right)\ge 4^{h+1}$ . This implies $d(2^{p_{1}p_{2}\cdot\cdot\cdot p_{n}p_{n+1}}+1)\ge 4^{h+1}$ , which completes the induction. QED

Resources

@@ Line 1: / Line 1: @@
 == Problem ==
-Let <math> p_{1}, p_{2}, \ldots , p_{n} </math> be distinct primes greater than 3.  Show that <math> 2^{p_{1}p_{2} \cdots p_{n}} + 1 </math> has at least <math> \displaystyle 4^n </math> divisors.
+Let <math> p_{1}, p_{2}, \ldots , p_{n} </math> be distinct primes greater than 3.  Show that <math> 2^{p_{1}p_{2} \cdots p_{n}} + 1 </math> has at least <math>4^n </math> divisors.
 == Solutions ==
@@ Line 7: / Line 7: @@
 === Solution 1 ===
-'''Lemma 1'''.  If <math> \displaystyle k > m </math>, then <math> \displaystyle km </math> has at least twice as many divisors as <math> \displaystyle m </math>.
+'''Lemma 1'''.  If <math>k > m </math>, then <math>km </math> has at least twice as many divisors as <math>m </math>.
-''Proof''.  For every divisor <math> \displaystyle a </math> of <math> \displaystyle m </math>, <math> \displaystyle ka </math> is clearly a divisor of <math> \displaystyle km </math>, but not <math> \displaystyle m </math>.
+''Proof''.  For every divisor <math>a </math> of <math>m </math>, <math>ka </math> is clearly a divisor of <math>km </math>, but not <math>m </math>.
-'''Lemma 2'''.  If <math> \displaystyle u </math> and <math> \displaystyle v </math> are [[relatively prime]] odd numbers, then the [[greatest common factor]] of <math> \displaystyle 2^u + 1 </math> and <math> \displaystyle 2^v + 1 </math> is 3.
+'''Lemma 2'''.  If <math>u </math> and <math>v </math> are [[relatively prime]] odd numbers, then the [[greatest common factor]] of <math>2^u + 1 </math> and <math>2^v + 1 </math> is 3.
-''Proof''.  Clearly, 3 divides both <math> \displaystyle 2^u + 1 </math> and <math> \displaystyle 2^v + 1 </math>.  Now, suppose that there is some <math> \displaystyle t > 3 </math> which divides both <math> \displaystyle 2^u + 1 </math> and <math> \displaystyle 2^v + 1 </math>.  Then <math> 2^u \equiv 2^v \equiv -1 \pmod{t} </math>.  But this means that both <math> \displaystyle u </math> and <math> \displaystyle v </math> are divisible by half the order of 2 in mod <math> \displaystyle t </math>, contradicting our assumption that <math> \displaystyle u </math> and <math> \displaystyle v </math> are relatively prime.
+''Proof''.  Clearly, 3 divides both <math>2^u + 1 </math> and <math>2^v + 1 </math>.  Now, suppose that there is some <math>t > 3 </math> which divides both <math>2^u + 1 </math> and <math>2^v + 1 </math>.  Then <math> 2^u \equiv 2^v \equiv -1 \pmod{t} </math>.  But this means that both <math>u </math> and <math>v </math> are divisible by half the order of 2 in mod <math>t </math>, contradicting our assumption that <math>u </math> and <math>v </math> are relatively prime.
 We now note that since
@@ Line 23: / Line 23: @@
 </center>
-we know that <math> \displaystyle 2^{uv} + 1 </math> is divisible by <math> \displaystyle 2^u + 1</math>, and, by symmetry, <math> \displaystyle 2^v </math> also, and therefore also by <math> \displaystyle (2^u + 1)(2^v +1)/3 </math>.
+we know that <math>2^{uv} + 1 </math> is divisible by <math>2^u + 1</math>, and, by symmetry, <math>2^v </math> also, and therefore also by <math>(2^u + 1)(2^v +1)/3 </math>.
-We now prove the result by induction on <math> \displaystyle n </math>.  Our base case, <math> \displaystyle n=1 </math>, is easy, since we know that <math> \displaystyle 2^{p_1} + 1 </math> is divisible by 3, and is greater than 27.  Now, set <math> u = p_{1}\cdots p_{n-1} </math> and <math> \displaystyle v = p_n </math>.  By Lemma 2, we know that <math> \displaystyle 2^{u} + 1 </math> and <math> \displaystyle 2^{v} + 1 </math> are relatively prime; hence <math> \displaystyle (2^u +1)(2^v + 1)/3 </math> has at least <math> \displaystyle 2 \cdot 4^{n-1} </math> factors, by the inductive hypothesis.
+We now prove the result by induction on <math>n </math>.  Our base case, <math>n=1 </math>, is easy, since we know that <math>2^{p_1} + 1 </math> is divisible by 3, and is greater than 27.  Now, set <math> u = p_{1}\cdots p_{n-1} </math> and <math>v = p_n </math>.  By Lemma 2, we know that <math>2^{u} + 1 </math> and <math>2^{v} + 1 </math> are relatively prime; hence <math>(2^u +1)(2^v + 1)/3 </math> has at least <math>2 \cdot 4^{n-1} </math> factors, by the inductive hypothesis.
-We know that <math> \displaystyle (2^u +1)(2^v + 1)/3 </math> divides <math> \displaystyle 2^{uv} + 1 </math>.  We also know that <math> \displaystyle uv > 2(u+v) </math>, whence <math> \displaystyle 2^{uv} > \left[ (2^u + 1)(2^v + 1)/3 \right]^2 </math>.  Then by Lemma 1,
+We know that <math>(2^u +1)(2^v + 1)/3 </math> divides <math>2^{uv} + 1 </math>.  We also know that <math>uv > 2(u+v) </math>, whence <math>2^{uv} > \left[ (2^u + 1)(2^v + 1)/3 \right]^2 </math>.  Then by Lemma 1,
 <center>
@@ Line 38: / Line 38: @@
 === Solution 2 ===
-We proceed by induction.  For our base case, <math> \displaystyle n = 1 </math>, we note that <math> 2^{p_1} </math> is divisible by 3.  Since <math> p_1 \ge 5 </math>, <math> 2^{p_1} </math> is clearly greater than 3 and cannot be a larger power of three, since this would require <math> p_1 \equiv 3 \pmod{6} </math>.  Therefore <math> 2^{p_1} + 1 </math> has some other prime factor and therefore at least 4 factors overall.
+We proceed by induction.  For our base case, <math>n = 1 </math>, we note that <math> 2^{p_1} +1 </math> is divisible by 3.  Since <math> p_1 \ge 5 </math>, <math> 2^{p_1} +1 </math> is clearly greater than 3 and cannot be a larger power of three, since this would require <math> p_1 \equiv 3 \pmod{6} </math>.  Therefore <math> 2^{p_1} + 1 </math> has some other prime factor and therefore at least 4 factors overall.
-Now, suppose the proposition holds for <math> \displaystyle n = k-1 </math>.  Without loss of generality, let <math> \displaystyle p_{k} </math> be the minimum of <math> \displaystyle p_{1}, \ldots , p_{k} </math>.  We shall abbreviate <math> q = \prod_{i=1}^{k-1}p_i </math>.  We note the relation
+Now, suppose the proposition holds for <math>n = k-1 </math>.  Without loss of generality, let <math>p_{k} </math> be the minimum of <math>p_{1}, \ldots , p_{k} </math>.  We shall abbreviate <math> q = \prod_{i=1}^{k-1}p_i </math>.  We note the relation
 <center>
@@ Line 48: / Line 48: @@
 </center>
-Since <math> \displaystyle 2^q + 1 </math> has at least <math> \displaystyle 4^{k-1}</math> factors, it will suffice to show that <math> \sum_{i=0}^{p_{k}-1} (-2)^{qi} </math> is relatively prime to <math> \displaystyle 2^q + 1 </math>, and has at least four factors.
+Since <math>2^q + 1 </math> has at least <math>4^{k-1}</math> factors, it will suffice to show that <math> \sum_{i=0}^{p_{k}-1} (-2)^{qi} </math> is relatively prime to <math>2^q + 1 </math>, and has at least four factors.
-We note that in general, <math> \sum_{i=0}^{p_{k}-1}(-x)^{i} </math> has remainder <math> \displaystyle p_k </math> when divided by <math> \displaystyle x+1 </math>.  But <math> \displaystyle p_k </math> cannot divide <math> \displaystyle 2^q + 1 </math>, as this would require <math> \displaystyle 2^q \equiv -1 \pmod{p_k-1}</math> when <math> \displaystyle q </math> is relatively prime to <math> \displaystyle p_k - 1 </math>.  Hence <math> \sum_{i=0}^{p_{k}-1} (-2)^{qi} </math> and <math> \displaystyle 2^q + 1 </math> are relatively prime.
+We note that in general, <math> \sum_{i=0}^{p_{k}-1}(-x)^{i} </math> has remainder <math>p_k </math> when divided by <math>x+1 </math>.  But <math>p_k </math> cannot divide <math>2^q + 1 </math>, as this would require <math>2^q \equiv -1 \pmod{p_k-1}</math> when <math>q </math> is relatively prime to <math>p_k - 1 </math>.  Hence <math> \sum_{i=0}^{p_{k}-1} (-2)^{qi} </math> and <math>2^q + 1 </math> are relatively prime.
-We now claim that <math> \sum_{i=0}^{p_{k}-1}(-2)^{qi} </math> has at least four factors.  We start by noting that in general, <math> \sum_{i=0}^{p_{k}-1} x^i </math> divides <math> \sum_{i=0}^{p_{k}-1} x^{qi} </math>, since the roots of the former are the nonreal <math> \displaystyle p_{k} </math>th [[roots of unity]] and <math> q \perp p_{k} </math>.
+We now claim that <math> \sum_{i=0}^{p_{k}-1}(-2)^{qi} </math> has at least four factors.  We start by noting that in general, <math> \sum_{i=0}^{p_{k}-1} x^i </math> divides <math> \sum_{i=0}^{p_{k}-1} x^{qi} </math>, since the roots of the former are the nonreal <math>p_{k} </math>th [[roots of unity]] and <math> q \perp p_{k} </math>.
 Since clearly <math> \sum_{i=0}^{p_{k}-1} (-2)^{qi} > \sum_{i=0}^{p_{k}-1} (-2)^i </math>, it is sufficient to show that the former is not the square of the latter (i.e., that the former is either a higher power of the latter, or some other prime divides the latter, either of which implies that the former has at least four factors).  But this follows from
@@ Line 59: / Line 59: @@
 <math>
 \begin{matrix}
-\displaystyle \sum_{i=0}^{p_{k}-1} (-2)^{qi} & > & 2^{q(p_{k}-1) - 1} \quad \\
+\sum_{i=0}^{p_{k}-1} (-2)^{qi} & > & 2^{q(p_{k}-1) - 1} \quad \\
 & > & \left( 2^{p_{k}} \right)^2 \qquad \quad \\
-& > & \displaystyle \left[ \sum_{i=0}^{p_{k}-1} (-2)^i \right]^2
+& > &\left[ \sum_{i=0}^{p_{k}-1} (-2)^i \right]^2
 \end{matrix}
 </math>
 </center>
-Thus <math> \sum_{i=0}^{p_{k}-1} (-2)^{qi} </math> has at least four factors and is relatively prime to <math> \displaystyle 2^{q} + 1 </math>, completing the induction.
+Thus <math> \sum_{i=0}^{p_{k}-1} (-2)^{qi} </math> has at least four factors and is relatively prime to <math>2^{q} + 1 </math>, completing the induction.
+=== Solution 3 ===
+We proceed by induction. Base case <math>n=1</math>. Observe that <math>3|2^{p_1}+1</math>, and since <math>p_1>3</math>, <math>2^{p_1}+1>9 \implies \frac{2^{p_{1}}+1}{3}>3</math> so <math>2^{p_1}+1</math> has at least 4 divisors.
+Now suppose the proposition holds for <math>n=h</math>.
+lemma 1:
+if <math>gcd(a,b)=1</math> with <math>a</math> and <math>b</math> both being odd, then <math>gcd(2^a+1,2^b+1)=3</math>.
+Proof:
+let p be a prime that divides both <math>2^a+1</math> and <math>2^b+1</math>. Then p divides both <math>2^{2a}-1</math> and <math>2^{2b}-1</math>. Since <math>2^{2a}\equiv 1</math> (mod <math>p</math>) and <math>2^{2b}\equiv 1</math> (mod <math>p</math>), <math>ord_{p}\left(2\right)</math> divides <math>2a</math> and <math>2b</math>. But, <math>gcd(a,b)=1</math>, so <math>ord_{p}\left(2\right)=2 \implies p=3</math>. Hence proven.
+lemma 2:
+<math>3||2^p+1</math>, with <math>p</math> being a prime greater than <math>3</math>.
+Proof;
+It suffices to show that <math>9\nmid 2^p+1</math>. for <math>0\le i\le8</math>, the only solution to <math>2^i+1\equiv 0</math> (mod <math>9</math>) is <math>i=3</math>. <math>6</math> is the smallest natural <math>k</math> such that <math>2^k-1\equiv 0</math> (mod <math>9</math>). This means that if <math>2^m+1\equiv 0</math> (mod <math>9</math>), <math>m\equiv 3</math> (mod <math>6</math>), but <math>p</math> is a prime greater than <math>3</math>, so this is not possible.
+Note that <math>\gcd\left(2^{p_{1}p_{2}\cdot\cdot\cdot p_{n}}+1,\ 2^{p_{n+1}}+1\right)=3</math>. Let <math>m=\frac{2^{p_{n+1}}+1}{3}</math>. Note that <math>\left(2^{p_{1}p_{2}\cdot\cdot\cdot p_{n}}+1\right)\left(2^{p_{n+1}}+1\right)<3\left(2^{p_{1}p_{2}\cdot\cdot\cdot p_{n}p_{n+1}}+1\right) \implies \left(2^{p_{1}p_{2}\cdot\cdot\cdot p_{n}}+1\right)m<\left(2^{p_{1}p_{2}\cdot\cdot\cdot p_{n}p_{n+1}}+1\right)</math>. So <math>2^{p_{1}p_{2}\cdot\cdot\cdot p_{n}p_{n+1}}+1=\left(2^{p_{1}p_{2}\cdot\cdot\cdot p_{n}}+1\right)mx</math>. Note that <math>gcd(m,2^{p_{1}p_{2}\cdot\cdot\cdot p_{n}}+1)=1</math>.
+I will now prove <math>x>2^{p_{1}p_{2}\cdot\cdot\cdot p_{n}}+1</math>. Note that <math>x=\frac{3\left(2^{p_{1}p_{2}\cdot\cdot\cdot p_{n}p_{n+1}}+1\right)}{\left(2^{p_{1}p_{2}\cdot\cdot\cdot p_{n}}+1\right)\left(2^{p_{n+1}}+1\right)}</math>. We wish to prove <math>x=\frac{3\left(2^{p_{1}p_{2}\cdot\cdot\cdot p_{n}p_{n+1}}+1\right)}{\left(2^{p_{1}p_{2}\cdot\cdot\cdot p_{n}}+1\right)\left(2^{p_{n+1}}+1\right)}>2^{p_{1}p_{2}\cdot\cdot\cdot p_{n}}+1</math>. Rearrange the inequality to get <math>\left(2+1\right)\left(2^{p_{1}p_{2}\cdot\cdot\cdot p_{n}p_{n+1}}+1\right)>\left(2^{p_{1}p_{2}\cdot\cdot\cdot p_{n}}+1\right)^{2}\left(2^{p_{n+1}}+1\right)</math>. Note that <math>p_{1}p_{2}\cdot\cdot\cdot p_{n}p_{n+1}+1>2p_{1}p_{2}\cdot\cdot\cdot p_{n}+p_{n+1}</math>, which implies the inequality. Since <math>x>2^{p_{1}p_{2}\cdot\cdot\cdot p_{n}}+1</math>,  <math>x\nmid 2^{p_{1}p_{2}\cdot\cdot\cdot p_{n}}+1</math>.
+Also, note that <math>2^{p_{1}p_{2}\cdot\cdot\cdot p_{n}}+1>m \implies x>m</math>. This means <math>mx</math> has at least four factors. Note that if <math>gcd(x,2^{p_{1}p_{2}\cdot\cdot\cdot p_{n}}+1)=1</math>, <math>mx</math> would be relatively prime to <math>2^{p_{1}p_{2}\cdot\cdot\cdot p_{n}}+1</math>, which would mean <math>2^{p_{1}p_{2}\cdot\cdot\cdot p_{n}p_{n+1}}+1</math> has at least <math>4\cdot4^{h}=4^{h+1}</math> factors.
+Assume <math>x</math> and <math>m</math> are not relatively prime. Then there exists some prime <math>q</math> such that <math>v_{q}\left(x\right)>v_{q}\left(2^{p_{1}p_{2}\cdot\cdot\cdot p_{n}}+1\right)</math>. Let <math>2^{p_{1}p_{2}\cdot\cdot\cdot p_{n}p_{n+1}}+1=q_{1}^{e_{1}}q_{2}^{e_{2}}\cdot\cdot\cdot q_{k}^{e_{k}}</math>, <math>m=pD</math> and <math>x=kq_{1}^{e_{1}+f}</math>, with <math>q_1</math> being the prime in question. Note that <math>f\ge1</math>. (<math>p</math> is relatively prime to <math>2^{p_{1}p_{2}\cdot\cdot\cdot p_{n}}+1</math>). Then <math>2^{p_{1}p_{2}\cdot\cdot\cdot p_{n}p_{n+1}}+1=q_{1}^{2e_{1}+f}q_{2}^{e_{2}}\cdot\cdot\cdot q_{k}^{e_{k}}p\cdot D\cdot k</math>. Let <math>d(n)</math> be the number of divisors of <math>n</math>. Then <math>d\left(q_{1}^{2e_{1}+f}q_{2}^{e_{2}}\cdot\cdot\cdot q_{k}^{e_{k}}p\cdot D\cdot k\right)\ge d\left(q_{1}^{2e_{1}+f}q_{2}^{e_{2}}\cdot\cdot\cdot q_{k}^{e_{k}}p\right)=\left(2e_{1}+f+1\right)\left(e_{2}+1\right)\cdot\cdot\cdot\left(e_{k}+1\right)\cdot2</math>. Note that <math>f+1\ge 2</math>, so
+<math>2e_{1}+f+1\ge2\left(e_{1}+1\right) \implies \left(2e_{1}+f+1\right)\left(e_{2}+1\right)\cdot\cdot\cdot\left(e_{k}+1\right)\cdot2\ge4\left(e_{1}+1\right)\left(e_{2}+1\right)\cdot\cdot\cdot\left(e_{k}+1\right)</math>. From the inductive step <math>d(2^{p_{1}p_{2}\cdot\cdot\cdot p_{n}}+1)=\left(e_{1}+1\right)\left(e_{2}+1\right)\cdot\cdot\cdot\left(e_{k}+1\right)\ge 4^h</math>, so <math>4\left(e_{1}+1\right)\left(e_{2}+1\right)\cdot\cdot\cdot\left(e_{k}+1\right)\ge 4^{h+1}</math>. This implies <math>d(2^{p_{1}p_{2}\cdot\cdot\cdot p_{n}p_{n+1}}+1)\ge 4^{h+1}</math>, which completes the induction.
+QED
-{{alternate solutions}}
 == Resources ==

Page

Toolbox

Search