18.10

Altheman

Let $A$ be the set of prime numbers dividing at least
one of the numbers $2^{n^2+1}-3^n$ . Prove that both $A$ and
$\mathbb{N}\backslash A$ are infinite.

**Posted:** Wed Jul 22, 2009 8:05 pm

_________________
-Alex
Altheman's Problem Column

fedja

Infiniteness of $A$ is easy. Suppose that there are only finitely many primes in $A$ . Note that $2,3\notin A$ . Let $P$ be the product of all elements of $A$ and let $a = \varphi(P)$ , Consider $n = am$ . Then our number $A_n = 2^{n^2 + 1} - 3^n$ is congruent to $B_m = 2^{a^2m^2 + 1} - 1$ modulo every $p\in A$ . Since every $A_n$ is divisible by some $p\in A$ , so is every $B_m$ . Thus, it remains to produce an infinite sequence of pairwise relatively prime $B_m$ , or, equivalently, of $D_m = a^2m^2 + 1$ . This can be done a la Euclid: put $m_1 = 1$ , $m_{j + 1} = \prod_{i < j}D_{m_i}$ .

**Posted:** Mon Jul 27, 2009 12:10 pm

fedja

OK, got it. Let $p$ be a prime divisor of $2^a-3$ with odd $a\ge 3$ of the form $8k\pm 3$ . Then $3^n\equiv 2^{an}\mod p$ , so, if $p|A_n$ , we must have $2^{n^2+1}\equiv 2^{an}\mod p$ but $n^2+1$ and $an$ have different parities, so $2$ must be a quadratic residue modulo $p$ , which is impossible. Now it remains to find infinitely many pairwise relatively prime numbers of the form $2^a-3$ with odd $a$ . But if $X_1,\dots,X_m$ are $m$ such numbers, then $2^{M\phi(X_1\dots X_m)+1}-3$ can be added to the list with any $M\ge 1$ .

**Posted:** Thu Jul 30, 2009 5:27 am

harazi

For the second part of the problem, one can also take any $p>3$ for which $2$ and $3$ are simultaneously non quadratic residues. It will work because $n$ and $n^2+1$ have different residues mod $2$ . This will probably use some trivial case of Dirichlet's theorem, though....

**Posted:** Wed Nov 04, 2009 8:54 am