Well, what I will say might seem weird, but $n$ and $n+1$ are co-prime, so their largest prime factors will be different. Doesn't this imply that $\exists$ infinitely many 'strange' pairs? @2below What is Kobayashi?

I only found 304 pairs during contest tho

Perhaps(rather probably) I’m wildly misinterpreting the problem, but why shouldn’t $n=p^{\alpha}$ with Kobayashi’s finish this off? What am I saying, just choosing $n=p$ kills this... there’s probably a typo in the problem...

I don't understand the question. Since $(n,n+1)=1$, $F(n)F(n+1)$ must be a product of two distinct primes. So trivial?

The problem statement is obviously wrong. I think that you need to proof that the complement of strange pairs is infinite. Or the definition should be adjusted.

Are you sure your statement is right?

actual problem wrote: For each integer $n \geq 2$, let $F(n)$ denote the greatest prime factor of $n$. A strange pair is a pair of distinct primes $p$ and $q$ such that there is $\textbf{no}$ integer $n \geq 2$ for which $F(n)F(n+1)=pq$. Prove that there exist infinitely many strange pairs.

Corrected problem statement; thanks @above

https://mathoverflow.net/questions/332901/greatest-prime-factor-of-n-and-n1 has a bit more on this problem.

Let $p$ and $q$ be primes such that $q \mid 2^p-1$ and $q\neq F(2^p-1).$ Clearly, there are infinitely many such primes $q.$ Suppose there exists an integer $m$ such that $F(m)F(m+1)=2q,$ then $m$ must be equal to $2^u-1$ for some $u.$ Now, $q$ divides $2^u-1$ iff $p$ divides $u,$ which would imply that $F(m)\neq q,$ hence we achieve a contradiction. EDIT: Whoops, this is wrong, we do not know if there are infinitely many composite numbers of the form $2^p-1$ for $p$ prime, see #2.

Should have spent more effort on problem 6 rather than problem 5 in the contest. Huge mistake Here's a solution with motivation: The condition of the problem somehow forces us to take either $p$ or $q$ being $2$. Otherwise, it is really hard to deal with something like $2^a \cdot 3^b \pm 1$. We will prove that the sufficient condition $o_p(2) = o_q(2)$ for two distinct primes $p > q$ implies that $(2,q)$ is strange. Claim 01. If $p$ and $q$ are distinct odd primes such that $o_p (2) = o_q (2)$ and $p > q$, then $(2,q)$ is strange. Proof. Notice that since either $F(n)$ or $F(n+1)$ is $2$, then we would have $n = 2^k$ or $n = 2^k - 1$. We would like to prove that for any $q$ such that $q | 2^k - 1$, then $F(2^k - 1) \not= q$, and for any $q$ such that $q | 2^k + 1$, we would have $F(2^k + 1) \not= q$. If $o_p (2) = o_q (2)$, then we would have $p | 2^k - 1$ as well if $q | 2^k - 1$. Hence, $F(2^k - 1) \ge p > q$. Furthermore, if $q | 2^k + 1$, then $q | 2^{2k} - 1$. Suppose $p | 2^k - 1$, then we would have $q | 2^k - 1$, as well, forcing $q | 2$, which is a contradiction. Hence, $p | 2^k + 1$ as well, which forces $F(2^k + 1) \ge p > q$. It suffices to prove that there are infinitely many distinct odd primes $p,q$ such that $o_p (2) = o_q (2)$. This is equivalent to finding infinitely many numbers $i$ such that $2^i - 1$ (or $2^i + 1$) have two distinct primes that doesn't appear in any $2^j - 1$, $j < i$ ($2^j + 1$). Now, dealing with order and stuffs motivates us to consider $i$ having as least divisors as possible. Playing with $2^i + 1$ has an advantage instead of $2^i - 1$ because it restricts the order of the primes, which is why I consider $2^i + 1$. Playing with $2^p + 1$ isn't helpful, as we can't factorized it (since we want something such that $2^i + 1$ produces at least 2 new prime, so factoring is a nice option.) Now, consider $2^{2p} + 1$. Since $p$ is odd. Then, by Sophie Germain Identity, we have \[ 2^{2p} + 1 = (2^p + 2^{\frac{p + 1}{2}} + 1)(2^p - 2^{\frac{p + 1}{2} } + 1) \]Now, consider the following lemma. $\textbf{Lemma 02.}$ If an odd prime $q$ satisfy $q | 2^{2p} + 1$, and $q \not= 5$, then $o_q (2) = 4p$. Proof. Notice that $q | 2^{4p} - 1$. Hence, $o_q (2) | 4p$. But if $o_q (2) | 2p$, then $q | 2^{2p} - 1$, which forces $q | 2$, a contradiction. Hence, we would have $o_q (2) \in \{ 4, 4p \}$. But if $o_q (2) = 4$, then we would have $q | 2^2 + 1 = 5$. But we assume that $q \not= 5$, hence we would have $o_q (2) = 4p$. Now, it's tempting to consider $p$ modulo $20$ since we would like to see the behavior of $2^{2p} + 1$ in modulo $25$. Now, notice that if $p \equiv 1 \ (\text{mod} \ 20)$, then we would have $2^{\frac{p + 1}{2}} \equiv 2, -2 \ (\text{mod} \ 25)$. Hence, one of $2^p + 2^{\frac{p + 1}{2}} + 1$ or $2^p - 2^{\frac{p + 1}{2}} + 1$ is $5$ modulo $25$, and the other is $1$ modulo $25$. Confirming that $2^p + 2^{\frac{p + 1}{2}} + 1 > 2^p - 2^{\frac{p + 1}{2}} + 1 > 5$ for any prime $p \equiv 1 \ (\text{mod} \ 20)$, and notice that both factors can't have the same odd prime divisor, since it would divide $2 \cdot 2^{\frac{p + 1}{2}}$. Then, each of these factors contribute a new prime $q$ with order $4p$. Therefore, we would have two distinct primes $q_1$ and $q_2$ such that \[ o_{q_1} (2) = o_{q_2} (2) = 4p \]We are hence finished. Remark. In the contest, my friend found a solution using $(2, G(2^{2^n} - 1))$ where $G(n)$ is the smallest prime factor of $n$, and $2^{2^n} - 1$ is composite. But unfortunately, the number of composite Fermat number remains open till now.

rmtf1111 wrote: Let $p$ and $q$ be primes such that $q \mid 2^p-1$ and $q\neq F(2^p-1).$ Clearly, there are infinitely many such primes $q.$ Suppose there exists an integer $m$ such that $F(m)F(m+1)=2q,$ then $m$ must be equal to $2^u-1$ for some $u.$ Now, $q$ divides $2^u-1$ iff $p$ divides $u,$ which would imply that $F(m)\neq q,$ hence we achieve a contradiction. EDIT: Whoops, this is wrong, we do not know if there are infinitely many composite numbers of the form $2^p-1$ for $p$ prime, see #2. Am i being dumb or doesnt Catalan Conjecture say this?

Catalan's conjecture says that no perfect powers are 1 apart, except for $8$ and $9$.

Solved with Th3Numb3rThr33. We will show there are infinitely many strange pairs of the form \((2,q)\). Claim: For primes \(q<r\), if \(\operatorname{ord}_q(2)=\operatorname{ord}_r(2)\) then \((2,q)\) is a strange pair. Proof. First note that for \(F(n)F(n+1)\) to be even, there must be a power of two among \(n\), \(n+1\), so \(n\) is either of the form \(2^k-1\) or \(2^k\). Therefore it suffices to show whenever \(q\mid2^k\pm1\) that \(F(2^k\pm1)\ne q\). Let \(d\) be the common order. Then: If \(q\mid2^k-1\), observe from \(2^d-1\mid2^k-1\) that \(F(2^k-1)\ge F(2^d-1)\ge r>q\). Suppose \(q\mid2^k+1\). Observe that for general primes \(p\), we have \(p\mid2^k+1\) if and only if \(\operatorname{ord}_p(2)\) is even and \(k\equiv\frac12\operatorname{ord}_p(2)\pmod{\operatorname{ord}_p(2)}\). Thus \(q\mid 2^k+1\iff k\equiv\frac12d\pmod d\iff r\mid2^k+1\), so \(F(2^k+1)\ge r>q\). Thus \((2,q)\) is strange. \(\blacksquare\) Select a large prime \(p\). First I claim we can find prime divisors \(5<q<r\) of \(2^{2p}+1\). Note that \(2^{2p}+1\) is not a multiple of three and \[\nu_5\left(2^{2p}+1\right)=\nu_5\left(4^p-(-1)^p\right)=1.\]By Sophie-Germain we have \[2^{2p}+1=\left(2^p-2^{(p+1)/2}+1\right)\left(2^p+2^{(p+1)/2}+1\right).\]These two factors are relatively prime. One of these factors is divisible by 5, so divide 5 out. Then what remains are two relatively prime divisors each with prime factors greater than 5, so \(q\) and \(r\) exist. Now note that \(\operatorname{ord}_q(2)=\operatorname{ord}_r(2)=4p\) (since neither order equals 4). We have exhibited infinitely many \(p\), and therefore infinitely many \(q\). This completes the proof.

Solution with awang11. We generate infinitely many primes $q$ for which $F(n)F(n+1)=2q$ has no solution. Let $p$ be a particular odd prime congruent to $3$ modulo $8$ (of which there are infinitely many by Dirichlet's Theorem on Arithmetic Progressions). Observe the factorization \[2^{2p}+1=(2^p-2^{(p+1)/2}+1)(2^p+2^{(p+1)/2}+1).\]Moreover, note the two factors are relatively prime, as they have difference $2^{(p+3)/2}$ which certainly divides neither. Since $p\equiv 3\pmod{8}$, we have $5\mid 2^p-2^{(p+1)/2}+1$ and $5\nmid 2^p+2^{(p+1)/2}+1$. Additionally, $5$ divides the expression exactly once by LTE. So let $q$ be the minimal prime divisor of $2^{2p}+1$ that is not $5$. Clearly $q$ is not also the largest prime factor of $2^{2p}+1$. Claim: $q\mid 2^k+1$ iff $2p\mid k,4p\nmid k$ and $q\mid 2^k-1$ iff $4p\mid k$. Solution: For the latter case, apply the Euclidean algorithm to see we get $q\mid 2^{\gcd(k,4p)}-1$. Clearly $\gcd(k,4p)=1,2,4$ cannot occur and neither can $\gcd(k,4p)=p,2p$ by assumption, so $4p\mid k$. For the former case, note $q\mid 2^{2k}-1$ so by the second part of the claim this implies $4p\mid 2k$, and clearly $4p\nmid k$. $\fbox{}$ Now, we argue that $F(n)F(n+1)=2q$ cannot occur. If $n=2^k$ for some $k$ then the claim suffices by showing $F(n+1)\ge F(2^{2p}+1)>q$ and similarly if $n=2^k-1$ for some $k$ then $F(n)\ge F(2^{2p}+1)>q$, since either way we get $q$ divides the $2^k\pm1$ term or we are automatically done. The primes $q$ generated are clearly distinct for each such prime $p$ because of the claim, so we are done.

Solved with rama1728. Claim: If for two odd primes $p < q$ we have $\operatorname{ord}_q(2) = \operatorname{ord}_p(2)$ then $(p,2)$ is strange. Proof: If $F(n)F(n+1)=2p,$ then either $(n,n+1)$ is either $(2^k, 2^k+1)$ or $(2^k-1, 2^k)$ for some positive integer $k.$ In the latter case, note $p \mid 2^{k}-1 \implies \operatorname{ord}_p(2) \mid k \implies \operatorname{ord}_q(2) \mid k \implies q \mid 2^k-1.$ In the former case, $p \mid 2^{k}+1 \implies \operatorname{ord}_p(2) =\operatorname{ord}_q(2) = 2k \implies q \mid 2^{2k}-1,$ and since $q \nmid 2^k-1$ because $\operatorname{ord}_q(2) \ne k,$ we have $q \mid 2^k+1.$ $\square$ It suffices to show there are infinitely many distinct pairs of odd primes $p,q$ where $\operatorname{ord}_q(2) = \operatorname{ord}_p(2).$ Take any prime $P = 2k+1 > 5$ (obviously infinitely many) and note \begin{align*} 2^{2P} + 1 &=4\cdot 2^{4k} + 1\\ &=(2^{2k+1}+2^{k+1}+1)(2^{2k+1}-2^{k+1}+1). \end{align*}Note $\gcd(2^{2k+1}+2^{k+1}+1, 2^{2k+1}-2^{k+1}+1)=\gcd(2^{k+2}, 2^{2k+1}-2^{k+1}+1)=1,$ $3 \nmid 2^{2P}+1,$ and $25 \nmid 2^{2P}+1$ since $10 \nmid 2P.$ So we can take two distinct primes $p,q > 5$ dividing $2^{2P}+1,$ so $\operatorname{ord}_q(2), \operatorname{ord}_p(2) \mid 4P.$ Obviously now $\operatorname{ord}_q(2), \operatorname{ord}_p(2) > 4,$ so $\operatorname{ord}_q(2) = \operatorname{ord}_p(2) = 4P$ as desired. $\blacksquare$

stupid silly problem. got all the right ideas until i didnt remember SOPHIE GERMAIN so i am dead lmao fascinating Consider numbers of the form $2^{2p}+1$ for $p$ an odd prime. Note that this number is always divisible by $5$ and never by $3$. Claim: For sufficiently large $p$, $2^{2p}+1$ has at least two prime divisors other than $5$. Proof: We use SOPHIE GERMAIN: $$2^{2p}+1=4\cdot (2^{\frac{p-1}{2}})^4+1^4=(2^p+2^{\frac{p+1}{2}}+1)(2^p-2^{\frac{p+1}{2}}+1).$$Both of these factors are integers, which are coprime (since their gcd divides $2^{\frac{p+3}{2}}$ by using the Euclidean algorithm) and larger than $5$ for all large enough $p$, which implies the desired result. $\blacksquare$ Now, in general, if $p \neq q$ are odd primes, then $$\gcd(2^{2p}+1,2^{2q}+1) \mid \gcd(2^{4p}-1,2^{4q}-1)=2^{\gcd(4p,4q)}-1=2^4-1=15,$$which implies that it is $5$. Therefore, we can find infinitely many primes $p>5$ such that $p$ divides $2^{2q}+1$ for some (unique) $q$ but $F(2^{2q}+1) \neq p$ by taking the smaller of the two prime divisors supplied by the above claim across all large $q$. I claim that, for these $p$, $(2,p)$ is always a strange pair. First note that $\mathrm{ord}_p(2)$ is either $4$ or $4q$, but the former would imply that $p \in \{3,5\}$, so it must equal $4q$. Now, if $F(n)F(n+1)=2p$ for some $n$, then either $n$ or $n+1$ is a power of $2$. In the first case, we would have $F(2^k+1)=p$ for some $k$. It is necessary (and sufficient) to have $k \equiv 2q \pmod{4q}$, but this implies that the other prime $p'>p$ dividing $2^{2q}+1$ also divides $2^k+1$: contradiction. In the second, we have $F(2^k-1)=p$ for some $k$. It is necessary (and sufficient) to have $k \equiv 0 \pmod{4q}$, but this again implies that $p'$ (as defined before) also divides $2^k-1$. This implies the desired result. $\blacksquare$

Well that was interesting. like @above, I got all the right ideas but focused on $2^p-1$ for prime $p$. I guess I didn't look at the big picture and realize that I needed an explicit factorization trick (new hard skill in the toolkit!)