## Task A-1.7.

Determine all natural numbers $n$ for which among the numbers $n, 4^{n}+1$, and $n^{2}+2$ at least two are prime numbers.
## Solution.

First, note that the number $4^{n}+1$ can only be prime if $n=1$ or if $n$ is even.

Indeed, for the values $n=1,2,3,4, \ldots$, the expression $4^{n}$ gives remainders $4,1,4,1, \ldots$ when divided by 5. Thus, when $n$ is odd, the number $4^{n}+1$ is divisible by 5, and thus is a composite number (except for $n=1$ when $4^{n}+1=5$).

For the last part, notice that if the number $n$ is not divisible by 3, then it is of the form $n=3k+1$ or $3k-1$. Then we have

$$
n^{2}+2=(3k \pm 1)^{2}+2=9k^{2} \pm 6k+3
$$

which means $n^{2}+2$ is a number divisible by 3.

1 point

Thus, $n^{2}+2$ can only be prime if $n$ is divisible by 3 (or if $n=1$, when this expression equals 3).

1 point

Now let's consider all cases:

1) The numbers $4^{n}+1$ and $n^{2}+2$ are both prime. For $n=1$, we get a solution (among the three numbers in the problem, two are prime: 5 and 3).

1 point

For $n>1$, from the above conclusions, we get that the number cannot be either even or odd, which means there are no more solutions in this case.

2) The numbers $4^{n}+1$ and $n$ are both prime. From the above conclusions, we know that the number cannot be an odd number. Therefore, $n$ must be even and prime, for which the only possibility is $n=2$. This is indeed a solution (among the three numbers, two are prime: 2 and 17).

2 points

3) The numbers $n^{2}+2$ and $n$ are both prime. From the above conclusions, we know that the number must be divisible by 3. However, $n$ is prime and divisible by 3 only in the case $n=3$. This is indeed a solution (among the three numbers, two are prime: 3 and 11).

Therefore, the desired numbers are $n=1,2,3$.

Note: The solution can be grouped into cases in many ways, but all solutions must be scored as above. Specifically:

- The statement that $4^{n}+1$ cannot be prime if $n$ is an odd number greater than 1 (total 2 points, where the statement and proof are worth 1 point each)
- The statement that $n^{2}+2$ cannot be prime if $n$ is even (1 point)
- The statement that $n^{2}+2$ cannot be prime if $n$ is not divisible by 3, or equal to 1 (total 2 points, where the statement and proof are worth 1 point each)
- The conclusion that $n=1$ is a solution (1 point), and for $n \neq 1$, the numbers $4^{n}+1$ and $n^{2}+2$ are not both prime (0 points)
- The conclusion that $n=2$ is a solution (1 point), and for $n \neq 2$, the numbers $4^{n}+1$ and $n$ are not both prime (1 point)
- The conclusion that $n=3$ is a solution (1 point), and for $n \neq 3$, the numbers $n^{2}+2$ and $n$ are not both prime (1 point).

The proof of the compositeness of $4^{n}+1$ can also be derived by factorization: if $n$ is an odd number greater than 1, then

$$
\left(4^{n}+1\right)=(4+1)\left(4^{n-1}-4^{n-2}+\cdots+1\right)
$$

is clearly a composite number.

## SCHOOL/CITY COMPETITION IN MATHEMATICS

2nd grade - high school - A variant

## February 17, 2021.

## IF A STUDENT HAS A DIFFERENT APPROACH TO SOLVING THE PROBLEM, THE COMMITTEE IS OBLIGED TO SCORE AND EVALUATE THAT APPROACH APPROPRIATELY.