Prove that for every given positive integer $k$, there exist infinitely many $n$, such that $2^{n}+3^{n}-1, 2^{n}+3^{n}-2,\ldots, 2^{n}+3^{n}-k$ are all composite numbers.
Problem
Source: 2009 China Western Mathematic Olmpiad
Tags: modular arithmetic, induction, number theory proposed, number theory
28.02.2012 20:45
It seems easy, because if we have one solution for some $k$ we can take with the chinese remainder theorem some numbers $\equiv n$ $\pmod{ (p-1)(q-1)\cdots}$ where $p,q,\cdots$ are numbers divising the terms. So we yet have to show there exist one such $n.$ This is trivial with induction, see $2^3+3^3-1$ until $32$ are composite, we have it is true for $k\ le 3$ now say the previous solutions with CRS where $n \equiv a \pmod{b}$ for $1$ to $k.$ Now take $p|2^a+3^a-(k+1)$ and take $b'=\frac{b(p-1)}{\gcd{b,p-1}}$ in the new modulor equation for the n's. (because $a$ works always and $2^{b'} \equiv 3^{b'}\equiv 1 \pmod{P}$ for each $P$ we had the numbers were multiples from/of, they keep being composite.
13.11.2014 18:34
SCP wrote: horizon wrote: Prove that for every given positive integer $k$, there exist infinitely many $n$, such that $2^{n}+3^{n}-1, 2^{n}+3^{n}-2,\ldots, 2^{n}+3^{n}-k$ are all composite numbers. So we yet have to show there exist one such $n.$ This is trivial with induction, see $2^3+3^3-1$ until $32$ are composite, we have it is true for $k\ le 3$ now say the previous solutions with CRS where $n \equiv a \pmod{b}$ for $1$ to $k.$ Now take $p|2^a+3^a-(k+1)$ and take $b'=\frac{b(p-1)}{\gcd{b,p-1}}$ in the new modulor equation for the n's. (because $a$ works always and $2^{b'} \equiv 3^{b'}\equiv 1 \pmod{P}$ for each $P$ we had the numbers were multiples from/of, they keep being composite. Can anyone explain in details please ? ?
13.11.2014 23:07
Fix $k\geq 1$ and take $m$ such that $2^m+3^m - k > 1$. Consider the set $P_m$ of all primes dividing at least one term $2^m+3^m-j$ for $1\leq j \leq k$, and take $\displaystyle n = m+ M\prod_{p\in P_m} (p-1)$ for positive integers $M\geq 1$. Then for each such $j$ there exists some $p\in P_m$ such that $2^m+3^m-j \equiv 0 \pmod{p}$, and then $2^n+3^n-j \equiv 2^m + 3^m - j \pmod{p}$. Since $p\leq 2^m + 3^m - j < 2^n + 3^n - j$, it means the terms $2^n+3^n-j$ are composite for $1\leq j \leq k$.