2. Let $k, n$ be natural numbers. For the statement “the number $(n-1)(n+1)$ is divisible by $k$,” Adam concluded that either the number $n-1$ or the number $n+1$ is divisible by $k$. Determine all natural numbers $k$ for which Adam's reasoning is correct for every natural $n$.


SOLUTION. We will show that for coprime natural numbers $r$ and $s$, where $r>2$ and $s>2$, there exists a natural number $n$ with the property

$$
r \mid n-1 \quad \text { and } \quad s \mid n+1 .
$$

For such a number $n$ and the number $k=rs$, Adam's reasoning is incorrect, because from the assumption that the number $k$ divides the number $(n-1)(n+1)$, it does not follow that $k$ divides $n-1$ or that $k$ divides $n+1$. If, for example, $k=rs$ divided $n-1$, it would divide the number $s$ both $n+1$ and $n-1$, which is impossible given the equality $(n+1)-(n-1)=2$, since $s>2$.

The existence of the number $n$ from the first sentence of the solution can be proven by considering $s$ numbers

$$
2, r+2, 2r+2, \ldots, (s-1)r+2 \text {. }
$$

These numbers give different remainders when divided by the number $s$. If, for example, two of them, say $ir+2$ and $jr+2(0 \leqq i<j \leqq s-1)$, gave the same remainder when divided by the number $s$, then the number $s$ would also divide their difference $(i-j)r$, and given the coprimality of the numbers $r$ and $s$, it would also divide the difference $i-j$, which is impossible because $|i-j|<s$. The $s$ numbers thus form a complete residue system modulo $s$, so there exists a number among them that gives a remainder of 0 when divided by $s$, let this number be $lr+2$. Then for the number $n=lr+1$, it holds that $r$ divides $n-1$ and $s$ divides $n+1$.

Let us realize that any number $k$ divisible by two odd primes can be written as the product of two coprime numbers greater than 2. Adam's reasoning can therefore be correct only for those numbers $k$ that are divisible by at most one odd prime. This means that the number $k$ has one of the following three forms:

$$
k=2^{s}, \quad k=p^{t}, \quad k=2p^{t},
$$

where $p$ is an odd prime, $s$ is a non-negative integer, and $t$ is a natural number.

Let $k=2^{s}$, where $s$ is a non-negative integer. For $s=0$, Adam's reasoning is incorrect, because the number $k=2^{0}=1$ divides every natural number, so it divides both numbers $n-1$ and $n+1$. For $s=1$, Adam's reasoning is also incorrect, because if $k=2^{1}=2$ divides the number $(n-1)(n+1)$, one of the factors is even, but then the other factor is also even. For the number $s=2$, i.e., for $k=2^{2}=4$, Adam's reasoning is correct. If 4 divides the number $(n-1)(n+1)$, at least one of the two factors is even, so they are two consecutive even numbers, of which exactly one is divisible by four. Finally, for any $s \geqq 3$, Adam's reasoning is incorrect, it suffices to take the number $n=2^{s-1}-1$.

Let $k=p^{t}$, where $p$ is an odd prime and $t$ is a natural number. Then Adam's reasoning is correct, because the numbers $n-1$ and $n+1$ cannot both be divisible by the same odd prime $p$, so exactly one of them is divisible by the number $p^{t}=k$.

Let $k=2p^{t}$, where $p$ is an odd prime and $t$ is a natural number. Then Adam's reasoning is also correct: the numbers $n-1$ and $n+1$ are necessarily even and cannot both be divisible by the same odd prime $p$, so exactly one of them is divisible by the number $2p^{t}=k$.

Conclusion. Adam's reasoning is correct for every natural number $n$ only for natural numbers $k$ of one of the forms

$$
k=4, \quad k=p^{t}, \quad k=2p^{t},
$$

where $p$ is an odd prime and $t$ is a natural number.

## GUIDING AND SUPPLEMENTARY PROBLEMS:

N1. If the number $(n-1)(n+1)$ is divisible by four, then exactly one of the factors $n-1, n+1$ is divisible by four. Prove it.

N2. Determine for which two-digit numbers $n$ the number $n^{3}-n$ is divisible by one hundred. $[50-\mathrm{C}-\mathrm{S}-3]$

N3. Find all three-digit numbers $n$ such that the last three digits of the number $n^{2}$ are the same as the number $n$. $[50-\mathrm{C}-\mathrm{I}-1]$

N4. How many natural numbers $x \leqq 1992000$ exist such that the number 1992000 divides the number $x^{3}-x ?[41-\mathrm{B}-\mathrm{I}-6]$