
2. Let $k, n$ be positive integers. Adam thinks, that if $k$ divides $(n-1)(n+1)$, then $k$ divides either $n-1$, or $n+1$. Find all $k$ for which the Adam's conclusion is correct for any $n$.

(Ján Mazák)


Solution. Let us begin with a

Lemma. Let $r>2$ and $s>2$ be relatively prime positive integers. Denote $k=r s$. There exists $n_{k}$ such that

$$
r \mid n_{k}-1 \quad \text { and } \quad s \mid n_{k}+1
$$

Proof. Consider $s$ numbers

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

which are pairwise non-congruent modulo $s$, and thus they form the complete residue set system modulo $s$. One of them, say $l r+2$, is therefore divisible by $s$. Then we let $n_{k}$ be $l r+1$.

The lemma shows that the sought $k$ s cannot be written as a product of two relatively prime numbers greater than 2 . Namely if $k=r s, r>2, s>2$ relatively prime, we choose $n=n_{k}$ and for this pair of numbers $k$ and $n$ is Adam wrong: then $k$ divides $(n-1)(n+1)$, but $k$ does not divide $n-1$ (since $s$ divides $n+1$ and $s>2$, $s$ does not divide $n-1$, thus neither does $k$ ) and analogously $k$ does not divide $n+1$.

Now any positive integer divisible by two odd primes can be written as a product of two relatively prime numbers greater than 2 . Thus the sought $k \mathrm{~s}$ have to be one of the following forms:

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

where $p$ is prime, $s$ non-negative integer, and $t$ positive integer.

If $k=2^{s}, s$ is positive integer, then $k=1$ and $k=2$ obviously do not comply. But $k=2^{2}=4$ is a solution: if 4 divides $(n-1)(n+1)$, then the factors are successive even numbers and thus just one of them is divisible by 4 . For $s \geqslant 3$ consider $n=2^{s-1}-1$ which proves Adam wrong.

Simple considerations show that $k=p^{t}$ and $k=2 p^{t}$ are solutions. Conclusion. The solutions of the problem are

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

where $p$ is odd prime and $t$ positive integer.
