Find all $n$ natural numbers such that for each of them there exist $p , q$ primes such that these terms satisfy. $1.$ $p+2=q$ $2.$ $2^n+p$ and $2^n+q$ are primes.
Problem
Source: Azerbaijan Balkan TST 2016 No 3
Tags: number theory
21.10.2016 04:17
I think modulo $3$ suffices here since $p$ and $q$ are distinct residues but $2^n$ is nonzero .-.
21.10.2016 10:51
Let $p>3$ Obvious $p=2$ mod $3$ Then $(2^n+p)(2^n+q) \equiv (2^n+2)(2^n+1) \equiv 0$ mod $3$, so $3|2^n+p$ or $3|2^n+q$ -contradiction. So $p=3,q=5$ Let $n>3$ $2^n+p\geq 19$ If $n=2k$ then $2^{2k}+5 \equiv 0$ mod $3$ - contradiction, so $n=2k+1$ If $n=4k+1$ then $2^{4k+1}+3=0$ mod $5$ so $n=4k+3$ $2^{4k+3}=16^k*8=2^k$ mod $7$ If $k=1$ mod $3$ then $2^{4k+3}+5=0$ mod $7$ - contradiction If $k=2$ mod $3$ then $2^{4k+3}+3=0$ mod $7$ - contradiction So $k=3l$; $n=12l+3$ $2^{12l+3}=8$ mod $13$ $2^{12l+3}+5=0$ mod $13$ -contradiction. So $n \leq 3$ For $n=1,3$ we get $(5,7)$ and $(11,13)$ - primes. Answer: $n=1,3$
20.07.2018 09:00
Different argument for beginning: Suppose $p,q > 3$, for some value of $n$, then $p,q \equiv \pm 1 \mod 6$. By the conditions, we must have $p \equiv -1 \mod 6, \ q \equiv 1 \mod 6$. One can easily see that $n=3$ is the minimal $n$ such that $2^n \equiv 2 \mod 6$, so it's sufficient to check all nonnegative $n$ less than $3$. $n=1 \implies 2^n+q \equiv 3 \mod 6,$ $n=2 \implies 2^n+p \equiv 3 \mod 6$, and the only prime that satisfies $3 \mod 6$ is $3$. However, our sum is strictly greater than $3$. Thus $p=3$ and $q=5$.
20.07.2018 09:41
More solutions: https://artofproblemsolving.com/community/c654464h1643076
01.02.2020 21:14
Amir Hossein wrote: More solutions: https://artofproblemsolving.com/community/c654464h1643076 so good
01.09.2021 05:19
The answer is $n=1,3$. Assume $p$ and $q$ are not divisible by $3$. Then, $p$ and $q$ are $1$ and $2\pmod3$, (not necessarily in that order). $2^n$ is either $1$ or $2\pmod3$. Thus, $2^n+p$ or $2^n+q$ is a multiple of $3$. It is easy to see that this isn't possible as $3$ is the only prime that is divisible by $3$. So either $p$ or $q$ are divisible by $3$. If $q=3$, then $p=1$, but $1$ is not a prime. Therefore, the only solutions for $p$ and $q$ are $p=3, q=5$. It remains to prove that we can't have any $n$ greater than $3$. Since, $2^n$ must be $2\pmod3$, $n$ is odd. Taking, $\pmod5$, we get that $n$ is not $1\pmod4$ unless $n=1$, which is a solution. So henceforth assume that $n\equiv3\pmod4$. First we take mod $7$. $2^n$ is not $4\pmod7$, so $n\ne2\pmod3$. We also find that $2^n$ is not $2\pmod7$ so $n\ne1\pmod3$. Thus, $3|n$. $n$ can be written as $3\pmod{12}$. Taking $\pmod{13}$ gives that $13|2^n+5$. So $2^n+5=13, 2^n=8 \implies {n=3}$, which also works as $11$ is also a prime.