Question: Let $m$ be a natural number. Show that there exists infinitely many primes $p$ of the form $p=4k+3$ such that $p$ divides at least one integer in the sequence $2^nm+1$; $n \in \mathbb{N}$.
My attempt: If $ p \mid 2^nm+1$ for some $n$, then we have
$ m \equiv \frac{-1}{2^n} \pmod{p}$ for some $n$. This is equivalent to $ m \equiv -2^{n'} \pmod{p}$ for some $n'$.
Hence, if we can show the existence of infinitely many primes of the form $4k+3$ of the sequence $m+2^n$, then we will be done. But this didn't seem any easier. Also,I realized that if $2$ is a primitive root modulo some $p$ then that $p$ divides some term of the sequence irrespective of $m$. But overall I couldn't get anything useful.
Best Answer
Using the $p$-adic order function, let
$$n_1 = \nu_2(m), \; m = 2^{n_1}m_1 \tag{1}\label{eq1A}$$
i.e., $m_1$ is an odd integer. Consider only integers $n_2 \gt n_1$, with $n = n_2 - n_1$. Using this, along what you've already shown, the original problem is equivalent to proving there's infinitely many primes of the form $4k + 3$ which divide values of the sequence
$$2^{n_2} + m = 2^{n_1}(2^{n_2-n_1} + m_1) = 2^{n_1}(2^{n} + m_1) \tag{2}\label{eq2A}$$
This shows we just need to consider the sequence $2^n + m_1$. In modulo $4$, compare the value with $n = 1$, i.e., $2 + m_1$, to $2^n + m_1$ for $n \ge 2$. The congruence values are $1$ and then $3$, or $3$ and then $1$. Note this means the parity of the number of prime factors of the form $4k + 3$ changes, with it being even when the value is $1$ modulo $4$ and odd when the value is $3$ modulo $4$.
Let $a$ be the number (possibly $0$) of distinct prime factors of $2 + m_1$ of the form $4k + 3$, with these being $p_i$ for $1 \le i \le a$. For some positive integer $b$ and exponents $r_i \ge 1$, this gives
$$2 + m_1 = b\prod_{i=1}^{a}p_i^{r_i} \tag{3}\label{eq3A}$$
Next, let
$$d_1 = \prod_{i=1}^{a}p_i^{r_i + 1} \tag{4}\label{eq4A}$$
Initialize $j = 1$, and then use Euler's totient function and Euler's theorem to get
$$e_{j} = 2^{\varphi(d_{j}) + 1} + m_1 \equiv 2 + m_1 \pmod{d_{j}} \tag{5}\label{eq5A}$$
The total number of factors of $p_i$, for $1 \le i \le a$, in $e_j$ is the same as $2 + m_1$. However, since $\varphi(d_{j}) + 1 \ge 2$ then, as discussed earlier, the parity of the number of factors of the form $4k + 3$ of $e_j$ is different, so there must be at least one more distinct prime factor the form $4k + 3$. In particular, note none of them are equal to any $b_i$ for $1 \le i \le a$, as well as to any $q_i$ for $1 \le i \le j - 1$. Choose $q_j$ among any of these new additional prime factors, and let
$$d_{j+1} = d_{j}q_{j} \tag{6}\label{eq6A}$$
Increment $j$ and then repeat the above procedure starting at \eqref{eq5A}.
Note for each $j \ge 1$, there is a new, distinct prime factor $q_j$ of $e_j$ in \eqref{eq5A} which is of the form $4k + 3$. Thus, repeating the above procedure an infinite number of times shows there are infinitely many different prime factors of the form $4k + 3$ among the values in the sequence $2^{n} + m_1$ and, thus, also in $2^{n}m + 1$.