Many years ago, a teacher who did not want to give a lecture ordered his students to calculate the sum of the numbers from 1 to 100. A very clever student named Gauss found a very simple way to accomplish the task by discovering the formula:

$$
1+2+3+\ldots+n=\frac{n(n+1)}{2}
$$

Since this story is from a long time ago, today's challenges given to students require more elaborate tasks.

(a) Verify that every prime number greater than 3 leaves a remainder of 1 or 5 when divided by 6.

(b) Verify that the sum of the prime numbers that are greater than 1 and less than 1000 is less than 166338.

(c) In the above estimate, to avoid technical complications, we did not eliminate some numbers that are certainly not prime. Eliminate some of these numbers and verify that the sum of the primes that are greater than 1 and less than 1000 is less than 166000.
Solution

(a) Let $p$ be a prime greater than 3. This prime, like any positive integer, can only leave remainders from 0 to 5 when divided by 6. Notice that if it left remainders of $0, 2, 3$, or 4, we could factor it:

$$
\begin{aligned}
& p=6 q+0=2 \cdot 3 q \\
& p=6 q+2=2 \cdot(3 q+1) \\
& p=6 q+3=3 \cdot(2 q+1) \\
& p=6 q+4=2 \cdot(3 q+2)
\end{aligned}
$$

Since $p$ is greater than 3, in each of the cases above it would be a composite number. Therefore, the only possible remainders of $p$ when divided by 6 are 1 and 5.
(b) To make an upper estimate, we can sum 2, 3, and all numbers that leave remainders of 1 or 5 when divided by 6. We will use the sum formula given in the problem statement and, for simplicity, represent a number that leaves a remainder of 5 as a multiple of 6 minus 1:

$$
\begin{aligned}
2+3+(6 \cdot 1-1)+(6 \cdot 1+1)+\ldots+(6 \cdot 166+1) & =5+12 \cdot(1+2+\ldots+166) \\
& =5+12 \cdot \frac{166 \cdot 167}{2} \\
& =5+166332 \\
& =166337
\end{aligned}
$$

Thus, the sum of the prime numbers less than 1000 is less than 166338.

(c) Among the numbers considered in the previous item, there are several that are not prime. Consider numbers that are multiples of 5 greater than 5 among those that leave a remainder of 1 or 5 when divided by 6. It is then sufficient to subtract some of these multiples of 5 less than 100 to improve the estimate:

$$
\begin{aligned}
25+35+55+65+85+95 & =60+120+180 \\
& =360
\end{aligned}
$$

And with this, we can conclude that the sum of the prime numbers less than 1000 is less than $166338-360<166000$.