## $[\quad$ Processes and Operations $\quad]$ [ Prime Numbers and Their Properties ] [ Decimal Number System ] $[$ Arithmetic of Residues (other). $]$

Initially, a prime number is displayed on the computer screen. Every second, the number on the screen is replaced by the number obtained from the previous one by adding 1 to its last digit. What is the maximum time it will take for a composite number to appear on the screen?
Let the initial number on the screen be 2, then we get the following sequence: $2-5-11-13-17$ - 25. The sixth number is composite, so in this case, it will take 5 seconds. We will prove that in other cases, it will take no more than 5 seconds.

Indeed, if the number on the screen was an odd prime number not ending in 9, then its last digit will change in a cycle:

$1-3-7-5-1$. This means that no later than 4 seconds, a number ending in 5 will appear. Since it is not equal to five, it is composite.

If the number on the screen was a prime number ending in 9, then 10 will be added every second. Since 10 gives a remainder of 1 when divided by 3, adding 10 once or twice will definitely result in a number divisible by 3. In this case, it will take no more than 2 seconds for a composite number to appear on the screen.

## Answer

## [ Decimal number system ] Problem 65688 Topics:  equations in integers $\quad]$  Factorization $\quad]$  [ Divisibility of numbers. General properties ]

Difficulty: $3+$

Grades: $9,10,11$

Author: Kosukhin O.N.

Find the smallest natural number whose decimal representation of the square ends in 2016.

## Solution

If the square of some natural number $n$ ends in 2016, then $n^{2}=10000 k+2016$ for some natural $k$. Then

$n^{2}-16=(n-4)(n+4)=10000 k+2000=2^{4} \cdot 5^{3}(5 k+1)$. The numbers $n-4$ and $n+4$ cannot both be divisible by 5, since their difference is 8. Therefore, either $n-4$ or $n+4$ is divisible by $5^3$. In addition, both numbers are even and divisible by 4, otherwise their product would not be divisible by $2^4$. This means that at least one of these numbers is divisible by $5^{3 \cdot 4}=500$, so $n=500 m \pm 4, n^{2}=250000 m^{2} \pm 4000 m+16$. If $m=1$, then $n^{2}$ ends in 6016 or 4016. If $m=2$ and the minus sign is chosen, we get the number $m=996$ - the smallest satisfying the condition of the problem, since $996^{2}=992016$.

## Answer

996.