Romanian Master of Mathematics

We show that there are infinitely many strange pairs of the form $\{2,q\}$ where $q$ is an odd prime.

The Lemma below provides a sufficient condition for such a pair to be strange. For an odd prime $q$, let $or{d}_q(2)$ denote the multiplicative order of $2$ modulo $q$, i.e., the least positive integer $s$ satisfying $q\mid 2^s-1$.

Lemma. If some primes $2<q_1<q_2$ satisfy $or{d}_{q_1}(2)=or{d}_{q_2}(2)$, then $\{2,q_1\}$ is a strange pair.

Proof. Arguing indirectly, suppose first that $2=gpf(n)$ and $q_1=gpf(n+1)$; in particular, $n=2^k$ for some positive integer $k$, and $q_1\mid 2^k+1$. This yields $q_1\mid 2^{2k}-1$, so $or{d}_{q_2}(2)=or{d}_{q_1}(2)\mid 2k$. Therefore, $q_2\mid 2^{2k}-1=(2^k-1)(2^k+1)$, but $q_2\nmid 2^k-1$, hence $q_2\mid 2^k+1$. So $gpf(n+1)\ge q_2$, which is a contradiction.

Similarly, but easier, if $2=gpf(n+1)$ and $q_1=gpf(n)$, then $n+1=2^k$, so $or{d}_{q_2}(2)=or{d}_{q_1}(2)\mid k$ and hence $q_2\mid 2^k-1$. Therefore, $gpf(n+1)\ge q_2$, a contradiction. $\square$

Let $p=2r-1>5$ be a prime, and let $N=2^{2p}+1$. We prove that:

(1) $N$ has at least two distinct prime factors greater than $5$;

(2) $or{d}_q(2)=4p$ for every prime factor $q>5$ of $N$.

Thus, every prime $p>5$ provides a pair of odd primes satisfying the conditions in the Lemma. Moreover, (2) shows that distinct primes $p>5$ provide disjoint such pairs, whence the conclusion.

To prove (1), notice that $3\nmid N$, and write $N=(4+1)(4^{p-1}-4^{p-2}+\cdots +1)\equiv 5p(\mathrm{mod}25)$, to infer that $25\nmid N$.

Next, write $N=(2^p+1{)}^2-2^{p+1}=(2^p-2^r+1)(2^p+2^r+1)$. The two factors are coprime (since they are odd, and their difference is $2^{r+1}$), and each is larger than $5$. Hence each has a prime factor greater than $5$. This establishes (1).

To prove (2), consider a prime factor $q>5$ of $N$, and notice that $or{d}_q(2)\mid 4p$, since $q\mid N\mid 2^{4p}-1$. If $or{d}_q(2)<4p$, then either $or{d}_q(2)\mid 2p$ or $or{d}_q(2)\mid 4$. The former is impossible due to $2^{2p}-1=N-2\equiv -2(\mathrm{mod}q)$, the latter — due to $q\nmid 15=2^4-1$. This establishes (2) and completes the proof.