14
$\begingroup$

Consider the set $$A=\{2^n+3^n\mid n\in \mathbb Z^+\}$$

Prove that the set of primes (call it $P$) dividing $A$ is infinite. (A prime is in $P$ iff it divides at least one element of $A$).

The "natural" way to do this is to assume the set $P=\{p_1,...,p_k\}$ is finite, and then construct an $n_o$ such that $2^{n_o}+3^{n_o}$ is divisible by a new prime not in $P$. But I tried a lot of things like $p_1p_2...p_k$ but they don't work. How am I supposed to approach this?

By the way this is just a special case of a more general problem. It replaces $2^n+3^n$ by $ab^n+cd^n$. But I think that solving the special case is enough to get an idea how to solve the general one.

$\endgroup$
12
  • 2
    $\begingroup$ There is a theorem stating that $a^n+b^n$ has a so-called primitive prime factor (meaning that $a^k+b^k$ is not divisible by the prime for any $k<n$) . This should help. $\endgroup$
    – Peter
    Jan 27, 2023 at 10:29
  • 5
    $\begingroup$ @Peter is referring to Zsigmondy's Theorem, see en.wikipedia.org/wiki/Zsigmondy%27s_theorem $\endgroup$ Jan 27, 2023 at 11:48
  • 2
    $\begingroup$ @PNT For this general case , we first need some restrictions. For the case $b=d$ , for example , we won't have infinite many prime factors in general. $\gcd(b,d)=1$ gives good chances that the claim holds, but this is probably out of reach to be solved. $\endgroup$
    – Peter
    Jan 27, 2023 at 12:12
  • 9
    $\begingroup$ For the special case, Fermat's little is enough. just take $n_0 = \prod\limits_{p\in P}(p-1)$. $\endgroup$ Jan 27, 2023 at 12:22
  • 2
    $\begingroup$ @Peter assume it's divisible by some prime $p_i\in P$ then $$2^{n_o}+3^{n_o}\equiv 2\pmod {p_i}$$ $\endgroup$
    – PNT
    Jan 27, 2023 at 14:04

5 Answers 5

13
$\begingroup$

Here's a solution to the special case quite similar in spirit to the strategy posed in the question body.

Suppose $p\mid 2^n+3^n$. We claim that, for any positive integer $k$, $p\nmid 2^{2kn}+3^{2kn}$. Indeed, $$2^{2kn}+3^{2kn}\equiv 2^{2kn}+(-2^n)^{2k}=2^{2kn}+2^{2kn}\equiv 2^{2kn+1}\pmod p$$ is not zero. So, suppose $\{p_1,\dots,p_s\}$ is a finite set of primes for which $p_i\mid 2^{n_i}+3^{n_i}$ for some integers $n_1,\dots,n_s$, and let $N=2n_1\cdots n_s$. We then have $$p_i\nmid 2^N+3^N$$ for each $1\leq i\leq s$. This means that the set of primes which divide numbers of the form $2^n+3^n$ cannot be finite.

$\endgroup$
5
$\begingroup$

For the special case, here is a beautiful construction given by @achille hui in the comments.

Assume the set $P=\{p_1,...,p_r\}$ is finite (Note that $P$ doesn't contain $2$ and $3$). Consider $$N=\prod_{i=1}^r(p_i-1)$$

By the assumption there exists a prime $p_k\in P$ such that $p_k\mid 2^N+3^N$. But $$2^N+3^N\equiv (2^{\frac{N}{p_k-1}})^{p_k-1}+(3^{\frac{N}{p_k-1}})^{p_k-1}\equiv 2\pmod{p_k}$$

Therefore $p_k=2$ which is a contradicition.

$\endgroup$
3
$\begingroup$

Regarding the general case of

$$g(n) = ab^n+cd^n \tag{1}\label{eq1A}$$

for a bit simpler handling, assume that $a$, $b$, $c$ and $d$ are all positive integers. Also, as Peter's comment indicates, it doesn't work with $b = d$, but we don't require $\gcd(b,d) = 1$. Next, define

$$\gcd(a,c) = e, \; \; a = ea_1, \; \; c = ec_1, \; \; \gcd(a_1,c_1)=1 \tag{2}\label{eq2A}$$ $$\gcd(b,d) = f, \; \; b = fb_1, \; \; d = fd_1, \; \; \gcd(b_1,d_1)=1 \tag{3}\label{eq3A}$$

Thus, we get

$$ab^n+cd^n = ef^n(a_{1}b_{1}^{n}+c_{1}d_{1}^{\,n}) \tag{4}\label{eq4A}$$

We therefore just need to prove there's infinitely many distinct prime divisors of $a_{1}b_{1}^{n}+c_{1}d_{1}^{n}$. Have $\gcd(a_1,d_1)=\gcd(b_1,c_1)=1$ and $\gcd(b_1,a_1+c_1)=\gcd(d_1,a_1+c_1)=1$ (however, my other answer shows these additional coprimality conditions are not required). Note your specific case of $g(n) = 2^n+3^n$ is handled within these restrictions.

Assume there's only a finite number of such prime divisors, and let $P$ be the set of all such primes that do not divide $a_1 + c_1$ (note this means these primes divide $g(n)$ for some $n \ge 1$ so, by the coprime conditions given earlier, none of these primes divide $b_1$ or $d_1$). Then using the Euler's totient function, define

$$n = \varphi\left((a_1+c_1)^2\prod_{p\in P}p\right) \tag{5}\label{eq5A}$$

We then get

$$g(n) \equiv a_1 + c_1 \pmod{(a_1+c_1)^2\prod_{p\in P}p} \tag{6}\label{eq6A}$$

This shows that no $p \in P$ divides $g(n)$. Also, using the $p$-adic valuation function (e.g., where $\nu_{p}(z)$ is the exponent of $p$ in the prime factorization of $z$), then for any prime $p \mid a_1+c_1$, we have $\nu_p(g(n))=\nu_p(a_1+c_1)$. Thus, $g(n) = a_1+c_1$, but $g(n) \gt a_1+c_1$. This contradiction shows the original assumption is incorrect, so there's actually an infinitely many prime factors which divide some $g(n)$.

$\endgroup$
2
  • 1
    $\begingroup$ Actually I just found that the problem is on aops. here's the link artofproblemsolving.com/community/c6h2751585p24027865. I read a couple of the answers but didn't understand them. $\endgroup$
    – PNT
    Jan 28, 2023 at 16:24
  • 1
    $\begingroup$ @PNT Thank you for pointing out that AoPS thread. As I mention in my other answer, which is based on one of those AoPS posts, most of the posts there have mistakes in them. This could be part of the reason you don't understand them (due to some lacking detail, I also found it somewhat challenging to understand them). However, I hope that my answer, which rearranges and expands on the other post, is something which you can understand. $\endgroup$ Jan 29, 2023 at 23:22
2
$\begingroup$

Regarding the general case of

$$f(n) = ab^n + cd^n \tag{1}\label{eq1B}$$

then with $a$, $b$, $c$ and $d$ being positive integers, the only requirement for the set of primes which divide $f(n)$ for at least one positive integer $n$ to be infinite in size is that $b \neq d$. As your comment indicates, the AoPS thread Exponential function with finitely many primes deals with this problem. However, most of the solutions there have various mistakes, in particular inappropriately assuming certain coprime conditions.

The following is a rearrangement, with some more details and other changes, of what's in post #6. First, as it states, and I've explained in more detail in my earlier answer, we can WLOG assume

$$\gcd(a,c) = \gcd(b,d) = 1 \tag{2}\label{eq2B}$$

Next, let $P$ be the set of primes which divide at least one of the values of the sequence $f(n)$ in \eqref{eq1B}. Assume $P$ has a finite number of elements, with $Q$ being the product of those primes which don't divide either $b$ or $d$. Note that $Q \gt 1$ since for any primes $p \in P$ which divide either $b$ or $d$, then the coprime conditions mean they divide $a$ (if $p \mid d$) or $c$ (if $p \mid b$). However, say for $p \mid d$ so $p \mid a$, then for large enough $n$ we have $\nu_p(ab^n +cd^n) = \nu_p(a)$, i.e., it's bounded above. This is also true for the other case. However, since $f(n)$ is unbounded, then it must have other prime factors, i.e., those used in producing the product $Q$.

Thus, for some integer $k \ge 1$, primes $q_i \in P$, any integer $j \ge 1$, and using Euler's totient function, we have

$$Q = \prod_{i=1}^{k}q_i, \;\; M = Q^{a+c}, \;\; s_{j} = j\varphi(M) \tag{3}\label{eq3B}$$

Thus, we also get

$$f(s_j) = ab^{s_j}+cd^{s_j} \equiv a + c \pmod{M} \tag{4}\label{eq4B}$$

This means there's an integer $r$ where $f(s_j) = a + c + rM$. The $a+c$ exponent used for $M$ in \eqref{eq3B} means, for any $q_i$ prime factor of $Q$, that $\nu_{q_i}(rM) \ge a + c$. Since $\nu_{q_i}(a+c) \lt a + c$, then $\nu_{q_i}(a+c) \lt \nu_{q_i}(rM)$, we get

$$\nu_{q_i}(f(s_j)) = \nu_{q_i}(a+c) \tag{5}\label{eq5B}$$

which means its bounded. This, along with the explanation earlier that the value of $\nu_p(f(n))$ for any prime $p \in P$ and $p \mid bd$ is also bounded, means the possible values of $f(s_j)$ are bounded, contradicting that $f(s_j)$ actually grows without bound. This contradiction means the finite assumption is incorrect, i.e., there are infinitely many elements in the set of primes $P$.

$\endgroup$
2
  • $\begingroup$ I'm not sure how (5) follows from the congruence. Is it because $\nu_{q_i}(f(s_j)-a-c)\ge a+c$ but if $\nu$ was really unbounded then for large enough $j$ We get $\nu_{q_i}(f(s_j)-a-c)=\nu_{q_i}(a+c)\ge a+c$ which is impossible? $\endgroup$
    – PNT
    Jan 30, 2023 at 12:17
  • $\begingroup$ @PNT First, I made a mistake. In $(5)$, it should've been $=$, not $\le$. Second, I added some explanation. When an integer is a sum of two terms, where the # of factors of a prime is less in one term than the other, then the integer's number of factors of that prime is that smaller value. In this case, $\nu_{q_i}(rM) \ge a + c$, but $\nu_{q_i}(a+c) \lt a + c$, so we have that $\nu_{q_i}(f(s_j)) = \nu_{q_i}(a+c)$. Thus, $f(s_j)$ has an upper bound on # of $q_i$ prime factors. However, $f(s_j)$ is composed only of primes which are bounded, but it's not bounded, so this is impossible. $\endgroup$ Jan 30, 2023 at 18:15
1
$\begingroup$

Comment : We can construct such n, for example take $p=13$ we may write:

$2^{12}\equiv 1\bmod 13\Rightarrow 2^{60}\equiv 1 \bmod 13$

Also:

$2^5\equiv 6\bmod 13 \Rightarrow 2^{10}\equiv -3\bmod 13$

Multiplying these relations we get:

$2^{70}\equiv -3\bmod 13$

Also we may write:

$3^3\equiv 1\bmod 13\Rightarrow 3^{69}\equiv 1 \bmod 13\Rightarrow 3^{70}\equiv 3\bmod 13$

summing these we get :

$2^{70}+3^{70}\equiv 0\bmod 13$

that is 13 is a prime factor of $2^{70}+3^{70}$

Another example; we use this question:

Find smallest composite n such that $2^n-2$ and $3^n-3$ be divisible by n.

The smallest n is 561 and next one is 1105, take this one; we may write:

$2^{1105}-2+3^{1105}-3 \equiv -5\bmod 1105\equiv 0\bmod 1105$

$1105=5\times 13\times 17$, So primes 5, 13 and 17 are factors of $2^{1105}+3^{1105}$

It is not known that these types of number are infinite but there are certainly more such number which can be found.

I do not think there is a limit for these numbers.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .