We need $ k_0k_1\cdots k_n = a(a + 1) + 1 = a^2 + a + 1$. Start with $ a^2 + a + 1 = (a - \varepsilon)(a - \overline\varepsilon)$, where $ \varepsilon = \cos \frac {2\pi}{3} + i \sin \frac {2\pi}{3}$. Then we would like to find $ b$ such that \[ (a^2 + a + 1)(b^2 + b + 1) = c^2 + c + 1, \] so we think that we need $ (a - \varepsilon)(b - \varepsilon) = ab + \overline\varepsilon - (a + b)\varepsilon$, so we need $ a + b = 0$, and so $ b = - a$, and we get \[ (a^2 + a + 1) (( - a)^2 + ( - a) + 1) = a^4 + a^2 + 1 \] and it's easy to see that $ a^2 + a + 1$ and $ a^2 - a + 1$ are coprime (as odd integers). Which implies that $ a^{2^n} + a^{2^{n - 1}} + 1$ will contain at least $ n + 1$ different prime factors, so we are done.

worthawholebean wrote: Prove that for each positive integer $ n$, there are pairwise relatively prime integers $ k_0,k_1,\ldots,k_n$, all strictly greater than $ 1$, such that $ k_0k_1\ldots k_n - 1$ is the product of two consecutive integers. That's a very old and fairly well-known problem. It goes (at least) back to Solomon W. Golomb: On certain nonlinear recurring sequences. Amer. Math. Monthly 70, (1963), 403-405.

CatalystOfNostalgia wrote:

My solution was similar, except it involved less thought.

My (lame) solution

Was anyone else stupid enough like me to overcomplicate the problem and show by induction how to explicitly construct $ k_0 k_1 \ldots k_n$ for each $ n$? I'm actually surprised I was able to get the whole thing down in one hour looking back on it.

Yes! I did that too. Like you must have 4k0k1...k(n-1)=s^2+3 so we take kn=s^2+2s+4.

MellowMelon wrote: Was anyone else stupid enough like me to overcomplicate the problem and show by induction how to explicitly construct $ k_0 k_1 \ldots k_n$ for each $ n$? I'm actually surprised I was able to get the whole thing down in one hour looking back on it. I actually proved a sequence $ k_i$ for which $ k_0...k_n-1$ is a product. It wasn't that bad. (Also, my sequence has k_0=3, so k_0-1=2=1*2 and so n=0 works in my sequence also.)

I'm not sure if this works, but: let $ k_1k_2\cdots k_n=x^2+x+1$ So we want to find infinitely many primes $ p$ such that $ x^2+x+1\equiv0\pmod p$ Since $ x$ is not $ 1 \pmod p$ except when $ x=3$, we can rewrite the above equation as $ x^3\equiv1\pmod p$ By FLT, $ x^{p-1}\equiv1\pmod p$ Since $ p$ is prime, we can take the roots of this and we see that the original equation must be true if $ 3$ divides $ p-1$, or $ p\equiv1\pmod3$. Since it is known that there are infinite primes $ 1\pmod3$, then it is proven. Doesn't that work?

MellowMelon wrote: Was anyone else stupid enough like me to overcomplicate the problem and show by induction how to explicitly construct $ k_0 k_1 \ldots k_n$ for each $ n$? I'm actually surprised I was able to get the whole thing down in one hour looking back on it. I did worse; for some random reason I thought I had to show that each of the $ k_i$s had to be prime .. and in the last half an hour I realized my mistake and fixed it.

just in your opinions, whats needed to get 1 point in this problem? if you preceded by induction for example...

nat mc wrote: I'm not sure if this works, but: let $ k_1k_2\cdots k_n = x^2 + x + 1$ So we want to find infinitely many primes $ p$ such that $ x^2 + x + 1\equiv0\pmod p$ Since $ x$ is not $ 1 \pmod p$ except when $ x = 3$, we can rewrite the above equation as $ x^3\equiv1\pmod p$ By FLT, $ x^{p - 1}\equiv1\pmod p$ Since $ p$ is prime, we can take the roots of this and we see that the original equation must be true if $ 3$ divides $ p - 1$, or $ p\equiv1\pmod3$. Since it is known that there are infinite primes $ 1\pmod3$, then it is proven. Doesn't that work? Can you take a root in a modulus? What I'm unsure about (though I'm probably missing something obvious) is $ x^{p-1}$ being able to imply $ x^{3}$, because $ x^{\frac{p-1}{3}}$ could be 1 mod p, right?

MellowMelon wrote: Was anyone else stupid enough like me to overcomplicate the problem and show by induction how to explicitly construct $ k_0 k_1 \ldots k_n$ for each $ n$? I'm actually surprised I was able to get the whole thing down in one hour looking back on it. Well, that's what I did, and it didn't take too long

nat mc wrote: I'm not sure if this works, but: let $ k_1k_2\cdots k_n = x^2 + x + 1$ So we want to find infinitely many primes $ p$ such that $ x^2 + x + 1\equiv0\pmod p$ This is not sufficient to prove the desired result. It could still be the case that the number of primes dividing $ x^2 + x + 1$ for a particular value of $ x$ is bounded. Follow-up: For what monic integer polynomials $ P(x)$ is it still true that the number of prime factors of $ P(n)$ is unbounded as $ n$ increases?

t0rajir0u wrote: This is not sufficient to prove the desired result. It could still be the case that the number of primes dividing $ x^2$ The chinese remainder theorem takes care of that pretty easily--if a_i^2+a_i+1 is a multiple of p_i, take a==a_i mod p_i for each 0<=i<=n.

I found a pretty nice/random seeming solution through a really intuitive step. Call a number $ X$ a good number of n-th degree if there exist $ k_0, .., k_n$ so that the conditions are satisfied, blah. Claim: Now define a sequence $ j$ such that $ j_1 = 4$ and $ j_n = (j_{n - 1} + 1)^2$. $ j_x(j_x + 1)$ is a good number of degree $ x$. It's true for $ x = 1$ because 3 * 7 - 1 = 4 * 5. Proof by induction: Assuming it's true for $ j_n$, let $ k_{n + 1} = j_n^2 + 3j_n + 3$, and then it's easy to prove that $ (k_{n + 1}, k_0 \cdot ... k_n) = 1$ and that the product of $ k_0$ through $ k_{n+1}$ is $ j_{n + 1}(j_{n + 1} + 1)$.

t0rajir0u wrote: Follow-up: For what monic integer polynomials $ P(x)$ is it still true that the number of prime factors of $ P(n)$ is unbounded as $ n$ increases? The official solutions document shows that if $ P(0) = 1$, and even if you drop the restriction that $ P$ is monic, you're good. Of course the solution set is probably far bigger. Actually I can't even think of a nonconstant polynomial for which that isn't true.

Actually being pairwise relatively prime is not needed; we can just pick $k$ that is sufficiently large.

Let $f(x)=x^2+x+1$. Check that $f\left(x^2\right)=f(x)f(x-1)$ and $\gcd(f(x),f(x-1))=1$, so $f\left(x^2\right)$ has strictly more prime factors than $f(x)$ for large enough $x$, so we can guarantee that $f\left(x^{2^{n-1}}\right)$ has at least $n$ distinct prime factors, done.

Note that by dirichlet's, there are infinitely many prime in the form $3k+1$. Let $p_0,p_1.\dots,p_n$ be distinct prime numbers in the form $3k+1$. Let $\omega_i$ be a primitive root modulo $p_i$. Then $p_i\mid \omega_i^{p-1}-1$ but $p_i\nmid \omega_i^{\frac{p-1}{3}}-1$ so $p_i\mid (w_i^{\frac{p-1}{3}})^2+w_i^{\frac{p_i-1}{3}}+1$. By CRT, there exist positive integers $x$ such that $x\equiv w_i^{\frac{p_i-1}{3}}\pmod{p_i}$ for all $i=0,1,\dots,n$. Hence $p_0p_1\dots p_n\mid x^2+x+1$ so $x^2+x+1$ has at least $n+1$ prime divisors, and we're done. Edit: Oops, in fact we don’t need primitive root. Schur’s kill it: we have that there are infinite many prime $p$ dividing $x^2+x+1$ for some $x$ and then do the same. (Use CRT)

yay Note that it sufficies to show that if $m$ is a positive integer, the number of distinct prime divisors of $m(m+1)+1$ is unbounded. This is because if $m(m+1)+1$ has at least $n+1$ distinct prime divisors, it is always possible to pick the $k_i$. We can rewrite this as $$\frac{m^3-1}{m-1}.$$Therefore, it is divisible by $p$ if $m^3\equiv 1\pmod p$ but $m\neq 1\pmod p.$ Claim: If $p$ is a prime for which $p\equiv 1\pmod 3$, then there exists $m$ such that $m^3\equiv 1\pmod p$ and $m\neq 1\pmod p.$ Let $r$ be a primitive root mod $p$. We can then pick $$m=r^{(p-1)/3}.$$ Pick a set of primes that are 1 mod 3. For each of these chosen primes $p$, pick a residue for $m\pmod p$ so that $m^3\equiv 1\pmod p$ but $m\neq 1\pmod p$ (which is possible due to our claim and the Chinese Remainder Theorem). This will guarantee that $\frac{m^3-1}{m-1}$ is divisible by every prime that we picked, so the number of prime divisors of $\frac{m^3-1}{m-1}$ is unbounded as we can pick any number of primes. Therefore, we are done.

CyclicISLscelesTrapezoid wrote: Let $f(x)=x^2+x+1$. Check that $f\left(x^2\right)=f(x)f(x-1)$ and $\gcd(f(x),f(x-1))=1$, so $f\left(x^2\right)$ has strictly more prime factors than $f(x)$ for large enough $x$, so we can guarantee that $f\left(x^{2^{n-1}}\right)$ has at least $n$ distinct prime factors, done. wait wow that is smart

Let $f(x)=x^2+x+1$. If we can prove that an infinite number of $p$ satisfy $p|f(x)$ for some $x$, then we are done by CRT. Now I claim that all $p \equiv 1 \pmod{3}$ work. Note it suffices to show that $p | \frac{x^3-1}{x-1}$. Assume $x \neq 1$, then we need $p|x^3-1 \implies x^3 \equiv 1 \pmod{p}$. It suffices to show there exists some $x\neq 1$ that satisfies this. To construct, consider a generator $g$, and note $g^{\frac{p-1}{3}}$ works. Thus, an infinite number of different primes divide $f(x)$, so by CRT, we can always form such a construction.

worthawholebean wrote: Prove that for each positive integer $ n$, there are pairwise relatively prime integers $ k_0,k_1,\ldots,k_n$, all strictly greater than $ 1$, such that $ k_0k_1\ldots k_n-1$ is the product of two consecutive integers. Take $k_0=3,k_1=7$ and $ k_0k_1\ldots k_n-1=a_n(a_n+1)$. Our objective is to construct $k_{n+1}$. Note that $$(a_n^2+a_n+1)k_{n+1}=a_{n+1}^2+a_{n+1}+1,$$so it suffices to construct $a_{n+1}$ such that $a_n^2+a_n+1$ divides $a_{n+1}^2+a_{n+1}+1$ and their quotient is relatively prime with $ k_0k_1\ldots k_n$. Firstly, let me prove that if $-3$ is quadratic residue modulo $p>3$, then $-3$ is also quadratic residue modulo $p^n$ for all $n$. Let $-3\equiv x_n^2\pmod{p^n}$ and pick $x_{n+1}\equiv \frac{x_n^p}{(-3)^\frac{p-1}{2}}\pmod{p^{n+1}}$, then$$x_{n+1}^2\equiv \frac{x_n^{2p}}{(-3)^{p-1}}\equiv\frac{(-3)^p}{(-3)^{p-1}}\equiv -3\pmod{p^{n+1}}$$as desired by the LTE lemma. $\square$ For convenience, let $x:=a_{n+1}, y:=a_n$ and $A=(2y+1)^2+3$. We need $y^2+y+1\mid x^2+x+1$ or $(2y+1)^2+3\mid (2x+1)^2+3$. Let $p_i$ be all prime divisors greater than $3$ of $A$. By the above lemma, there exists $b_i$ such that $p_i^{\nu_{p_i} (A)+1}\mid b_i^2+3$. Let $c_i=kb_i$, where $$k\equiv 1-p_i^{\nu_{p_i} (A)}\pmod{p_i^{\nu_{p_i} (A)+1}},$$then $$c_i^2\equiv -3k^2\equiv -3+6p_i^{\nu_{p_i} (A)}\pmod{p_i^{\nu_{p_i} (A)+1}}.$$Note that $A\equiv 3\pmod{9}$ or $3\nmid A$, so by the CRT, there exists an (infinitely) $x'$ such that$$\begin{cases} x'\equiv c_i\pmod{p_i^{\nu_{p_i} (A)+1}}\\ x'\equiv 0\pmod{3}\\ x'\equiv 1\pmod 2 \end{cases}$$Combining with the fact that $y^2+y+1$ is odd, we get $\nu_{p_i}(y^2+y+1)=\nu_{p_i}(x^2+x+1)$ and the conclusion follows.

Mathematically, $\forall n \in \mathbb{Z}, \exists k_{0}, k_{1} \dots k_{n}, (k_{i}, k_{j} ) = 1, \text{s.t } k_0k_1\ldots k_n-1 = x(x+1)$ Sorry I just wanted to look cool. The basically only remotely useful part is that $k_0k_1\ldots k_n-1 = x(x+1)$ We can now rewrite as $k_0k_1\ldots k_n = x(x+1) + 1 = x^2 + x + 1$ Key Step: Because these are all relatively prime, $k_0k_1\ldots k_n$ has atleast $n+1$ prime factors Our condition can now be rewritten as "we want to find $z$ such that $z^2 + z + 1$ has $n+1$ prime factors We can guaruntee this, by proving that the set of primes which divide $z^2 + z + 1$ is infinite. We can now imitate Euclid's infinitude primes. Assume FTSOC that the set of primes which divide $z^2 + z + 1$ is finite. Let $z = p_0p_1\ldots p_n$, the product of those primes Now we know that $z^2 + z + 1$ is prime, and $z^2 + z + 1$ is not one of the aformentioned $p_{i}$. Contradiction We have now proved the original.

It suffices to show that the quantity $n^2 + n + 1$ is divisible by an arbitrarily large number of distinct primes as we vary $n$. In fact, we prove this for primes whch are $1 \pmod{3}$. For such primes, consider $n$ such that $$n \equiv g_p^{\frac{p-1}{3}} \pmod{p},$$where $g_p$ is the primitve root $\pmod{p}$, and combine the equations for all such $p$ using the Chinese Remainder Theorem. $\square$

OG! A very beautiful one! Consider the polynomial $P(x)= x^2+x+1$. Observe that $P(x^2)=(x^2+x+1)(x^2-x+1)=(P(x))(x^2-x+1)$$(identity -OG)$ Claim: $P(2^{2^k})$ can be represented as the product of $k$ pairwise coprime integers. Proof: We induct over $k$, $k=1$ is trivial. So, assume The Claim is true for $k=m$, then $P(2^{2^m})=a_1.a_2. \cdots a_m = ({(2^{2^m})}^2+{2^{2^m}}+1)$. where all $a_i$ are pairwise coprime for all $1 \leq i \leq m$ So, for $k=m+1, P(2^{2^{m+1}})=P({(2^{2^m})}^2)=P((2^{2^m}))({(2^{2^m})}^2-{2^{2^m}}+1)=({(2^{2^m})}^2+{2^{2^m}}+1)({(2^{2^m})}^2-{2^{2^m}}+1)$. $gcd(a_1.a_2. \cdots a_m, {(2^{2^m})}^2-{2^{2^m}}+1)=gcd({(2^{2^m})}^2+{2^{2^m}}+1,{(2^{2^m})}^2-{2^{2^m}}+1)= gcd({(2^{2^m})}^2+{2^{2^m}}+1, 2^{2^m+1})=1$. set $({(2^{2^m})}^2-{2^{2^m}}+1)=a_{m+1}$, hence $a_{m+1}$ is coprime to each of $a_1 \cdots a_m$. Hence, $P(2^{2^{m+1}})= a_1.a_2 \cdots a_{m+1}$ where all $a_i$ are pairwise coprime for all $1 \leq i \leq m+1$. Hence our induction is done. Now, for all positive integral $n$ $P(2^{2^n})=a_1.a_2. \cdots a_n$, where all $a_i$ are pairwise coprime for all $1 \leq i \leq n$ so $a_1.a_2. \cdots a_n-1 =l(l+1)$ where $l= 2^{2^n}$ as desired. Hence we have have found $n$ pairwise co- prime integers, which satisfy the condition, for all positive integral $n$ as desired.

We create this inductively. For the base case n = 1 take $k_0 = 3,k_1 = 7$. Assume we can find $k_i$ for all $m\leq n-1$. And that the $a$ in the next lines is even (our base case satisfies this) Then $$ k_{0} \cdot k_{1} \cdots k_{n-1} = a^2 + a +1 $$For some $a$. Next take $k_n = a^2 - a +1$. This works as $(a^2 - a +1,a^2 + a +1) = 1$ as $a$ is even. The coprimitiveness gives us a new prime as well so the condition is satisfied.

Call a prime special if it divides some value of $x^2 + x + 1$, where $x$ is a positive integer. Claim: There are infinitely many special primes. Proof: Follows by Schur or 2009 N3. $\square$ Claim: The number of prime divisors of $x^2 + x + 1$ is unbounded as $x$ varies over positive integers. Proof: Let $x_1, x_2,\ldots, x_t$ be $t$ different good primes for any positive integer $t$. Now let $r_1, r_2, \ldots, r_t$ satisfy $r_i^2 + r_i + 1 \equiv 0 \pmod{x_i}$. Fix some number $M$ that is $r_i \pmod{x_i}$ for each $1 \le i \le t$ (exists by CRT). Notice that $x_i\mid M^2 + M + 1$ for each $i$, so $M^2 + M + 1$ has at least $t$ different prime divisors. $\square$ Now fix some $N > n$ so that we can find a positive integer $x$ where $x^2 + x + 1$ has $N$ prime divisors. Call them $p_0, p_1, \ldots, p_{N - 1}$. Now let $c_i = p_i^{\nu_{p_i}(x^2 + x + 1)} > 1$ for each integer $0 \le i \le N - 1$. We have $c_0 \cdot c_1 \cdots c_{N - 1} = x^2 + x + 1$ and the $c_i$ are pairwise relatively prime to each other. Consider $k_i = c_i \forall 0 \le i \le n - 1$ and $k_n = \prod_{i=n}^{N-1} c_i$. It's clear that all the $k_i$ are greater than $1$ and pairwise relatively prime to each other. Their product is $\prod_{i=0}^{N-1} c_i = x^2 + x + 1$, so \[ k_0 k_1 \cdots k_n - 1 = x^2 + x = x(x+1),\]as desired.

Let $f(x) = x^2 + x + 1$, and let $a_n = 1434^{2^n}$ for every integer $n$. Note that $a_{n + 1} = a_n^2$. Claim: For any positive integer $n$, $f(a_n)$ has at least $n$ distinct prime divisors. Proof. We proceed via induction. The base case is trivial, so just focus on $n \geq 2$. Now \[\gcd(f(a_n), f(a_n - 1)) = \gcd(a_n^2 + a_n + 1, a_n^2 - a_n + 1) = \gcd(2a_n, a_n^2 - a_n + 1).\]Since $a_n$ is always even, we can let $a_n = 2b_n$. Thus this is equal to \[\gcd(4b_n, 4b_n^2 - 2b_n + 1) = \gcd(4b_n, 2b_n + 1) = \gcd(2b_n - 1, 2b_n + 1) = \gcd(2b_n - 1, 2) = 1.\]Hence, there exists a prime $p$ that divides $f(a_n - 1)$ but not $f(a_n)$ since $f(a_n - 1) > 1$ obviously. But \[f(a_n) f(a_n - 1) = (a_n^2 + a_n + 1)(a_n^2 - a_n + 1) = a_n^4 + a_n^2 + 1 = f(a_n^2) = f(a_{n + 1}),\]so $pf(a_n) \mid f(a_n) f(a_n - 1) = f(a_{n + 1})$. The left-hand side has $n + 1$ prime divisors, so the right-hand side has at least $n + 1$ prime divisors, as desired. $\square$ Hence we can let $a_{n + 1} = p_1^{\alpha_1} p_2^{\alpha_2} \dotsm p_r^{\alpha_r}$ for distinct primes $p_1$, $p_2$, $\dots{}{}$, $p_r$ and an integer $r \geq n + 1$. Now just set $k_i = p_{i + 1}^{\alpha_{i + 1}}$ for all $1 \leq i \leq n - 1$ and $k_n = p_{n + 1}^{\alpha_{n + 1}} p_{n + 2}^{\alpha_{n + 2}} \dotsm p_r^{\alpha_r}$, whence the $k_i$ are all obviously relatively prime and $k_0 k_1 \dotsm k_n - 1 = a_{n + 1}(a_{n + 1} + 1)$.

Let $p_0, p_1, \dots, p_{n}$ be the first $n+1$ primes which are $1\pmod3$. By Dirichlet's Theorem, there are infinitely many such primes. Let $g_t$ be any primitive root in $\pmod{p_t}$ for all $0\le t\le n$. Consider $a$ such that $a\equiv g_t^{\frac{p_t-1}3}\pmod{p_t}$ so $a^3\equiv 1\pmod{p_t}$ for all $0\le t\le n$. Then, $a(a+1)+1=a^2+a+1=\frac{a^3-1}{a-1}\equiv 0\pmod{p_t}$ for all $0\le t\le n$. Let $k_t=p_{t}^{v_{p_t}(a(a+1)+1)}$ for all $1\le t\le n$. Let $k_0=\frac{a(a+1)+1}{k_1\dots k_n}$. This completes our proof.