$7^{7^{k}}+1|7^{7^{n}}+1, k=0,1,...,n$ and for k>0 $\frac{7^{7^{k}}+1}{7^{7^{k-1}}+1}$ had at least 2 prime divisors $p_{1},p_{2}$, suth that $p_{i}\not |7^{7^{k-1}}+1$.

With that, you would have probably got 1 point.

I have the same idea of you, Rust! But i can't find how to prove that $a^{6}-a^{5}+a^{4}-a^{3}+a^{2}-a+1$ isn't prime, for $a = 7^{7^{k}}$ This is the unique problem in USAMO that i didn't obtain one solution.

Look the equation in reverse direction $1-a+a^{2}-a^{3}+a^{4}-a^{5}+a^{6}$, now you can find something.

kunny wrote: Look the equation in reverse direction $1-a+a^{2}-a^{3}+a^{4}-a^{5}+a^{6}$, now you can find something. Please, kunny, say anything more directly! I don't understand how this will help me.

N.T.TUAN wrote: Prove that for every nonnegative integer $n$, the number $7^{7^{n}}+1$ is the product of at least $2n+3$ ($not \ necessarily \ distinct$) primes. for n=0 we have $8=2*2*2$ it is true. Therefore it following by induction if $f(a)=a^{6}-a^{5}+a^{4}-a^{3}+a^{2}-a+1$ is not prime for $a=7^{7^{k}},k=0,1,...$ Concider prime $113=1+16*7$. We have $7=c^{8}(mod \ 113)$ (because $113|7^{7}+1$), therefore for any k $113|f(a),a=7^{7^{k}}$. Obviosly $\frac{f(a)}{113}>1$.

Here is my solution .Let $A(n)=7^{7^{n}}+1$ . By induction we assume that it has 2n+3 divisors Then \[A(n+1)=((A(n)-1)^{7}+1=A(n)((A(n))^{6}-7(A(n))^{5}+21(A(n))^{4}-35(A(n))^{3}+35(A(n))^{2}-21(A(n))+7)\] Now see the coefficients -7,21,-35,35,-21,7 we have a symmetry . So we can factor after $(A(n))^{6}$ . Indeed $A(n+1)=A(n) ((A(n))^{6}-7(A(n)-1)((A(n))^{2}-A(n)+1)^{2})$ Now observe that $7(A(n)-1)=7^{7^{n}+1}=7^{2k}$ So it is a perfect square and so $7(A(n)-1)((A(n))^{2}-A(n)+1)^{2})$ is also a perfect square and so $((A(n))^{6}-7(A(n)-1)((A(n))^{2}-A(n)+1)^{2})$ is a difference of squares so it is a product of two numbers so +2 prime factors So $A(n+1)$ has $2+2n+3=2(n+1)+3$ factors . QED

It give at least $7^{7^{n}}+1=2*2*2*113*113*...._{n \ times}p_{1}*...*p_{2n-1}$ - multiple 3n+2 primes.

Interesting, Silouan! Your solution is exactly the same of the oficial's one! Congratulations for this nice solution!

Rust wrote: N.T.TUAN wrote: Prove that for every nonnegative integer $n$, the number $7^{7^{n}}+1$ is the product of at least $2n+3$ ($not \ necessarily \ distinct$) primes. for n=0 we have $8=2*2*2$ it is true. Therefore it following by induction if $f(a)=a^{6}-a^{5}+a^{4}-a^{3}+a^{2}-a+1$ is not prime for $a=7^{7^{k}},k=0,1,...$ Concider prime $113=1+16*7$. We have $7=c^{8}(mod \ 113)$ (because $113|7^{7}+1$), therefore for any k $113|f(a),a=7^{7^{k}}$. Obviosly $\frac{f(a)}{113}>1$. Let me see Rust, we have that $113|7^{7}+1$ so $113|7^{7^{k}}+1$,yes? So $a\equiv (-1)(mod 113)$,thus $f(a)\equiv 7(mod113)$,am I right? then how did you get that $113|f(a)$?

Tiks wrote: Rust wrote: Let me see Rust, we have that $113|7^{7}+1$ so $113|7^{7^{k}}+1$,yes? So $a\equiv (-1)(mod 113)$,thus $f(a)\equiv 7(mod113)$,am I right? then how did you get that $113|f(a)$? Yes, you are right. It is my mistake. From $p|7^{7^{k}}+1$ we get $f(a)\equiv 7(mod \ p)$ for $a=7^{7^{k}}$. Therefore we have $2n$ distinct (because from silouan solution we get A(n+1)/A(n) is not degree of prime) odd prime divisors $A(n)=7^{7^{n}}+1.$

Let's generalize the result. Claim: For any prime $ p$, such that $ p \equiv 3 \mod 4$, then $ p^{p^n} + 1$ has at least $ 2n + 2$ prime divisors, not necessarily all of which are distinct. Proof: Induction. For $ n = 1$, $ p + 1$ is a multiple of $ 4$, and has at least $ 2$ divisors. It remains to prove, that $ \frac {p^{p^n} + 1} {p^{p^{n - 1}} + 1}$ has at least 2 prime divisors. Consider Lucas's Theorem for $ p$ a prime, such that $ p \equiv 3 \mod 4$. (http://mathworld.wolfram.com/LucassTheorem.html). Since the cyclotomic polynomial $ \Phi_{p} (x) = \frac {x^p - 1}{x - 1}$, we have: $ \frac {x^p - 1}{x - 1} = (R(x))^2 + px (S(x))^2$, for some integer polynomials $ R(x)$ and $ S(x)$, such that $ R(x), S(x)$ have degrees $ \frac {p - 1}{2}, \frac {p - 3}{2}$, respectively. Now, let $ x = - p^{p^{n - 1}}$. We have: $ \frac {p^{p^n} + 1} {p^{p^{n - 1}} + 1} = (R(x))^2 - p^{p^{n - 1} + 1} (S(x))^2 = [R(x) - qS(x)][R(x) + qS(x)]$, where $ q = p^{\frac {p^{n - 1} + 1} {2} }$. Thus we are done, since we have shown, $ \frac {p^{p^n} + 1} {p^{p^{n - 1}} + 1}$, is the product of at least 2 primes.

I remember sketching epitomy01's general way somewhere, probably in another thread concerning this problem. Nontheless, see http://www.mathlinks.ro/Forum/viewtopic.php?t=146020 for Lucas' formula.

epitomy01 wrote: Since the cyclotomic polynomial $ \Phi_{p} (x) = \frac {x^p - 1}{x - 1}$, we have: $ \frac {x^p - 1}{x - 1} = (R(x))^2 + px (S(x))^2$, for some integer polynomials $ R(x)$ and $ S(x)$, such that $ R(x), S(x)$ have degrees $ \frac {p - 1}{2}, \frac {p - 3}{2}$, respectively. What? Is that a general property of cyclotomic polynomials? Can you direct me to a proof of that? Also, does anyone know of a way to come up with the difference of squares given here in solution 2 that is not completely out of the blue? That is, what is the motivation for getting to $ (x^{3} + 3x^{2} + 3x + 1)^{2} - 7x(x^{2} + x + 1)^{2}$ ? I noticed that the first term is (x+1)^6. Is there a similar factorization that extends to $ \sum_{k=0}^n (-1)^k x^n$ for n other than 6?

Lots of induction proofs. Are there any other type of proofs, like by contradiction (assume it has less than taht many factors) ? Rust isn't using induction which is neat.

FibonacciFan,see the link I gave ( http://www.mathlinks.ro/Forum/viewtopic.php?t=146020 ).

epitomy01 wrote: We have: $ \frac {p^{p^n} + 1} {p^{p^{n - 1}} + 1} = (R(x))^2 - p^{p^{n - 1} + 1} (S(x))^2 = [R(x) - qS(x)][R(x) + qS(x)]$, where $ q = p^{\frac {p^{n - 1} + 1} {2} }$. Thus we are done, since we have shown, $ \frac {p^{p^n} + 1} {p^{p^{n - 1}} + 1}$, is the product of at least 2 primes. How do we know that none of these factors is 1?

For every special case, this is trivial. In general, you will have to consider some inequalities, using a little bit more information on the factors. See http://www.mathlinks.ro/Forum/viewtopic.php?t=169135 .

Note that \[ \frac{x^7+1}{x+1} = (x+1)^6 - 7x(x^2+x+1)^2 \] which is a difference of two squares if $x=7^{7^k}$. Then it's trivial.

@v_Enhance, what is your motivation for $(x+1)^6$, instead of something in the form $(x^3+ax^2+bx+1)^2$? (Sorry if this is obvious)

Isn't this trivial by Zsigmondy?

math2468 wrote: Isn't this trivial by Zsigmondy? Can you please provide a proof by Zsigmondy?

math2468 wrote: Isn't this trivial by Zsigmondy? I don't think so... Zsigmondy's guarantees one new prime per $n$... However, you require two (not necessarily new) primes per $n$, so Zsigmondy's can't really be applied here

What is the motivation for factoring $\frac{7^{7^{n+1}}+1}{7^{7^n}}$? Thanks a lot!

AMN300 wrote: @v_Enhance, what is your motivation for $(x+1)^6$, instead of something in the form $(x^3+ax^2+bx+1)^2$? (Sorry if this is obvious)

$(x+1)^6 = (x^3 + 3x^2 + 3x + 1)^2$

v_Enhance wrote: Note that \[ \frac{x^7+1}{x+1} = (x+1)^6 - 7x(x^2+x+1)^2 \]which is a difference of two squares if $x=7^{7^k}$. Then it's trivial. Dear v_enhance when factor how only 2 prime not more?

The problem asks to show it's the product of at least $2n+3$ primes. So it's fine if there are more.

Sorry to bump a 3-year old thread but what's the motivation behind $\frac{x^7 + 1}{x+1} = (x+1)^6 - 7x(x^2 + x + 1)^2$? For post #26, what's the motivation behind difference of squares? I understand that this would give the two extra factors, but it seems like a slightly random factorization to choose. Thanks!

Jay17 wrote: Sorry to bump a 3-year old thread but what's the motivation behind $\frac{x^7 + 1}{x+1} = (x+1)^6 - 7x(x^2 + x + 1)^2$? For post #26, what's the motivation behind difference of squares? I understand that this would give the two extra factors, but it seems like a slightly random factorization to choose. Thanks! We choose that since it proves that each successive expression is divisible by previous and another number which is not prime

And it is random. You can also say that x=7^7^n + 1 and then write for n+1, and you’ll see a similar trick works

We claim that the fraction $\frac{7^{7^{n+1}} + 1}{7^{7^n}+1}$ is composite. This solves the problem, $7^{7^0} + 1 = 8$ is the product of $3$ primes, and we can finish by induction. Let $x=7^{7^n}$. Take note that $7x$ is a square. The fraction is \[ \frac{x^7+1}{x+1} = x^6 - x^5 + x^4 - x^3 + x^2 - x + 1.\]The identity $\binom{p-1}{k} \equiv (-1)^k \pmod{p}$ and the fact that $7x$ is a square motivates us to write the above expression as the difference of two squares, one of which is $(x+1)^6$, which would imply that the expression is composite. But notice that \[ x^6 - x^5 + x^4 - x^3 + x^2 - x + 1 = (x+1)^6 - 7x(x^4+2x^3+3x^2+2x+1) = (x+1)^6 - 7x(x^2+x+1)^2,\]so we are done. $\blacksquare$

epitomy01 wrote: Let's generalize the result. Claim: For any prime $ p$, such that $ p \equiv 3 \mod 4$, then $ p^{p^n} + 1$ has at least $ 2n + 2$ prime divisors, not necessarily all of which are distinct. Proof: Induction. For $ n = 1$, $ p + 1$ is a multiple of $ 4$, and has at least $ 2$ divisors. It remains to prove, that $ \frac {p^{p^n} + 1} {p^{p^{n - 1}} + 1}$ has at least 2 prime divisors. Consider Lucas's Theorem for $ p$ a prime, such that $ p \equiv 3 \mod 4$. (http://mathworld.wolfram.com/LucassTheorem.html). Since the cyclotomic polynomial $ \Phi_{p} (x) = \frac {x^p - 1}{x - 1}$, we have: $ \frac {x^p - 1}{x - 1} = (R(x))^2 + px (S(x))^2$, for some integer polynomials $ R(x)$ and $ S(x)$, such that $ R(x), S(x)$ have degrees $ \frac {p - 1}{2}, \frac {p - 3}{2}$, respectively. Now, let $ x = - p^{p^{n - 1}}$. We have: $ \frac {p^{p^n} + 1} {p^{p^{n - 1}} + 1} = (R(x))^2 - p^{p^{n - 1} + 1} (S(x))^2 = [R(x) - qS(x)][R(x) + qS(x)]$, where $ q = p^{\frac {p^{n - 1} + 1} {2} }$. Thus we are done, since we have shown, $ \frac {p^{p^n} + 1} {p^{p^{n - 1}} + 1}$, is the product of at least 2 primes. thank you for that

We prove the result by induction (base cases $n=0$ and $n=1$. We will show that $7^{7^{n+1}}+1$ has adds at least two prime factors to $7^{7^n}+1$. Then, if $7^{7^n}+1$ is the product of $2n+3$ primes, then $7^{7^{n+1}}+1$ is the product of $2n+5=2(n+1)+3$ primes, which will complete the induction. If we let $7^{7^n}=k$, we have $7^{7^{n+1}}=k^7$. \[k^7+1=(k+1)(k^6-k^5+k^4-k^3+k^2-k+1)\] It suffices to show $k^6-k^5+k^4-k^3+k^2-k+1$ is not a prime for any $n$. We have \[k^6-k^5+k^4-k^3+k^2-k+1=(k+1)^6-7k(k^2+k+1)^2 \] This is equal to $((k+1)^3-7^{\frac{7^n+1}{2}}(k^2+k+1))((k+1)^3+7^{\frac{7^n+1}{2}}(k^2+k+1))$. It suffices to show that the term \[((k+1)^3-7^{\frac{7^n+1}{2}}(k^2+k+1))\ne 1\]because the product of two primes greater than $1$ is always composite. Note that $7^n\ge \frac{7^n+1}{2}$, so \[((k+1)^3-7^{\frac{7^n+1}{2}}(k^2+k+1))\ge (k+1)^3-k(k^2+k+1)=k^3+3k^2+3k+1-k^3-k^2-k=2k^2+2k+1>1,\]as desired.

We use induction with the base case of $n=0$ being evident. Now suppose this is true for $n$, and let $x=7^{7^n}$. Then $$\frac{x^7+1}{x+1}=x^6-x^5+x^4-x^3+x^2-x+1=(x+1)^6-7x(x^2+x+1)^2.$$Since $7x=7^{7^n+1}$ which is a square, it follows that $(x+1)^6-7x(x^2+x+1)^2$ can be written as the difference of two squares, and thus can be written as the product of two numbers (neither of which are one), hence there are at least $2$ primes dividing $\tfrac{x^7+1}{x+1}$, so there are at least $2n+5=2(n+1)+3$ primes dividing $7^{7^{n+1}}+1$. $\blacksquare$

Notice $x^7+1=(x+1)(x^6-x^5+x^4-x^3+x^2-x+1)$ so $$7^{7^n}+1=(7^{7^0}+1)\prod_{i=0}^{n-1}(x_i^6-x_i^5+x_i^4-x_i^3+x_i^2-x_i+1),$$where $x_i=7^{7^i}.$ Then, $2^3\mid 7^{7^0}+1,$ so it suffices to show $x_i^6-x_i^5+x_i^4-x_i^3+x_i^2-x_i+1$ has at least two prime factors for all $i.$ We see $$x_i^6-x_i^5+x_i^4-x_i^3+x_i^2-x_i+1=(x_i+1)^6-7(x_i^5+2x_i^4+3x_i^3+2x_i^2+x)=(x_i+1)^6-7x_i(x_i^2+x_i+1)^2,$$a difference of squares since $x_i$ is seven raised to an odd power. Noting both factors cannot be one finishes. $\square$

The factorization idea has appeared before in ISL 1992. https://artofproblemsolving.com/community/c146h150528p849468

Wow. Let $$a_n=7^{7^n}+1.$$Clearly, $a_0=8$ has at a value of 3. Now, we will use induction. Clearly, $a_{n+1}$ is a multiple of $a_n$. It then suffices to show that $a_{n+1}/a_n$ is not prime (since then it would have a value of at least 2 more than $a_n$). Let $P=7^{7^n}.$ We have $$\frac{a_{n+1}}{a_n}=\frac{P^7+1}{P+1}=P^6-P^5+P^4-P^3+P^2-P+1$$$$=(P+1)^6 - (7P^5+14P^4+21P^3+14P^2+7P)$$$$=(P+1)^6-7P(P^2+P+1)^2.$$Now, note that since $7P=7^{7^n+1},$ and $7^n+1$ is even, $7P$ is a perfect square. This makes the expression a difference of squares. Since the difference between $(P+1)^3$ and $(\sqrt{7P})(P^2+P+1)$ is larger than 1, this can be factored as the product of two numbers larger than 1, so it is not prime. Therefore, $a_{n+1}$ has a value of at least 2 more than $a_n$, so we are done by induction.

Loved the problem. It is trivial that we have to show that $a^6-a^5+a^4-a^3+a^2-a+1$ is not a prime and we will do it by factorizing it.where $a= 7^{7^n}$ \begin{align*} &a^6-a^5+a^4-a^3+a^2-a+1 \\ &= a^6+6a^5+15a^4+20a^3+15a^2+6a+1 - 7(a^5+2a^4+3a^3+2a^2+a) \\ &= a^6-a^5+a^4-a^3+a^2-a+1-7a(a^2+a+1)^2 \end{align*}which is difference of two squares and no square is $1$

Does this work? We will use induction. In fact, we need to prove that $\frac{x^7+1}{x+1}$ isn't prime for $x=7^{7^k}$. But $\frac{x^7+1}{x+1} = \Phi_6(-7^{7^k})=\Phi_{7^k\cdot 6}(-7) \cdot \Phi_6(-7^{7^{k-1}})$ and, of course, $\Phi_6(-7^{7^k}) > \Phi_6(-7^{7^{k-1}}) >1$, so $\Phi_6(-7^{7^k})$ isn't prime.

\begin{align} \frac{x^7+1}{x+1} &= x^6-x^5+x^4-x^3+x^2-x+1\nonumber \\ &=(x+1)^6-7x(x^5+2x^4+3x^3+2x^2+x)\nonumber \\ &=(x+1)^6-7x(x^2(x^2+x+1)+(x^2+x+1)+x(x^2+x+1))\nonumber \\ &=(x+1)^6-7x(x^2+x+1)^2\nonumber \end{align}So plugging $x=7^{7^n}$ gives $\frac{7^{7^{n+1}}+1}{7^{7^n}+1}$ equal to a difference of squares, i.e a no prime number, so $7^{7^{n+1}}+1$ has at least two more divisors than ${7^{7^n}+1}$, now we can do induction to prove the desired.

We proceed to prove by induction on $n$. Note that the base case $n=1$ is trivial. Assume that the result holds for some positive integer $n$. We will prove that it holds for $n+1$ too. Let $a=7^{7^n}$. Then: $$ a^7+1 = (a+1)(a^6-a^5+a^4-a^3+a^2-a+1)$$From inductive hypothesis, $a+1$ already at-least $2n+1$ prime factors. Thus, it suffice to show that: $S = a^6-a^5+a^4-a^3+a^2-a+1$ is a composite number, in-order for $a^7+1$ to have $2n+3$ prime factors. Notice that: $$S = (a+1)^6-7a(a^2+a+1)^2 = ((a+1)^3 - \sqrt{7a} (a^2+a+1)) \cdot ((a+1)^3 + \sqrt{7a} (a^2+a+1))$$It suffice to show that: $(a+1)^3 - \sqrt{7a} (a^2+a+1) > 1$ inorder to have $S$ to be a composite number. Notice that: $(a+1)^3 - \sqrt{7a} (a^2+a+1) > (a+1)^3 - a (a^2+a+1) = 2a^2+2a+1 > 1$. Hence $S$ is a composite number and therefore, the induction is complete as $a^7+1$ has at-least $2n+3$ prime factors.

First, rewrite $7^{7^n} + 1$ as \[(7 + 1)\left(\sum_{k = 0}^{7^n - 1} 7^k\right)\] Obviously, $8$ has three prime factors, so now we aim to show that \[\sum_{k = 0}^{7^n - 1} 7^k\] has $2n$ prime factors. We will use induction. The base case ($n = 0$) holds, so now we will show that if \[\sum_{k = 0}^{7^n - 1} 7^k\] has $2n$ factors, then \[S = \sum_{k = 0}^{7 \cdot 7^n - 1} 7^k\] has $2n + 2$ factors. $S$ can be factored as follows: \[\left(\sum_{k = 0}^{6} (-7)^{k \cdot 7^n}\right)\left(\sum_{k = 0}^{7^n - 1} (-7)^k\right)\] From the inductive step, $\sum_{k = 0}^{7^n - 1} (-7)^k$ has at least $2n$ prime factors. Thus, we must show that $S_1 = \sum_{k = 0}^{6} (-7)^{k \cdot 7^n}$ has at least $2$ prime factors. Let $x = 7^{7^n}$. Then $S_1$ can be rewritten as \[\frac{x^7 + 1}{x+1} = (x+1)^6 - 7x(x^2 + x + 1)\] Since $7 \cdot 7^{7^{n}}$ has an even exponent, we can apply difference of squares to see that $S_1$ indeed has at least two distinct factors, as desired. This completes the induction, and thus $S$ has at least $2n$ prime factors $\forall n \in \mathbb{N}_0$ (implying that $7^{7^{n}} + 1$ has at least $2n + 3$ prime factors $\forall n \in \mathbb{N}_0$).