3. Find the number of natural numbers $k$, not exceeding 291000, such that $k^{2}-1$ is divisible by 291.
Answer: 4000.

Solution. By factoring the dividend and divisor, we get the condition $(k-1)(k+1):(3 \cdot 97)$. This means that one of the numbers $(k+1)$ or $(k-1)$ is divisible by 97. Let's consider two cases.

a) $(k+1): 97$, i.e., $k=97 p+96, p \in \mathrm{Z}$. Then we get $(97 p+95)(97 p+97):(3 \cdot 97) \Leftrightarrow(97 p+95)(p+1): 3$. The first factor is divisible by 3 when $p=3 q+1, q \in \mathrm{Z}$, and the second when $p=3 q+2, q \in \mathrm{Z}$, from which we obtain that $k=291 q+193, k=291 q+290, q \in \mathrm{Z}$.

b) $(k-1): 97$, i.e., $k=97 p+1, p \in \mathrm{Z}$. Then we get $97 p(97 p+2):(3 \cdot 97) \Leftrightarrow(97 p+2) p ; 3$. The first factor is divisible by 3 when $p=3 q+1, q \in \mathrm{Z}$, and the second when $p=3 q, q \in \mathrm{Z}$, from which we obtain that $k=291 q+98$, $k=291 q+1, q \in \mathrm{Z}$.

Thus, the numbers that satisfy the condition of the problem are those that give remainders of $193, 290, 98, 1$ when divided by 291, meaning that every 4 out of 291 consecutive numbers fit. Since $291000=291 \cdot 1000$, we get $4 \cdot 1000=4000$ numbers.