4. Let $p, q (p<q)$ be given natural numbers. Determine the smallest natural number $m$ with the property: The sum of all fractions in simplest form, which have denominator $m$ and whose values lie in the open interval $(p, q)$, is at least $56\left(q^{2}-p^{2}\right)$.

The regional round of category A takes place

## on Tuesday, January 23, 2007

so that it starts in the morning and contestants have 4 hours of pure time to solve the problems. For each problem, contestants can earn 6 points, and a successful solver is a student who scores 10 points or more. Allowed aids are writing and drawing supplies, school MF tables, and calculators without a graphical display. This information will be communicated to the students before the start of the competition.
4. We will show that the smallest $m$ is 113 (independent of the values of $p, q$). Let's assume $m>1$. For any natural numbers $c, d$, let $S_{m}(c, d)$ denote the sum of all fractions in simplest form that lie in the open interval $(c, d)$ and whose denominator is $m$. Then the inequality holds:

$$
S_{m}(c, c+1) \leqq\left(c+\frac{1}{m}\right)+\left(c+\frac{2}{m}\right)+\ldots+\left(c+\frac{m-1}{m}\right)=(m-1) c+\frac{m-1}{2}
$$

where equality holds if and only if all numbers $1,2, \ldots, m-1$ are coprime with $m$, i.e., if and only if $m$ is a prime number.

For given natural numbers $p, q$ and $m>1$, we have

$$
\begin{aligned}
S_{m}(p, q)= & S_{m}(p, p+1)+S_{m}(p+1, p+2)+\ldots+S_{m}(q-1, q) \leqq \\
\leqq & \left((m-1) p+\frac{m-1}{2}\right)+\left((m-1)(p+1)+\frac{m-1}{2}\right)+\ldots \\
& +\left((m-1)(q-1)+\frac{m-1}{2}\right)= \\
= & (m-1) \frac{(q-p)(p+q-1)}{2}+(m-1) \frac{q-p}{2}= \\
= & (m-1) \frac{q-p}{2}(p+q-1+1)=\frac{(m-1)\left(q^{2}-p^{2}\right)}{2},
\end{aligned}
$$

thus

$$
S_{m}(p, q) \leqq \frac{(m-1)\left(q^{2}-p^{2}\right)}{2}
$$

Equality in relation (9) holds if and only if $m$ is a prime number. According to the problem statement, however,

$$
S_{m}(p, q) \geqq 56\left(q^{2}-p^{2}\right)
$$

Considering relation (9), we see that necessarily $\frac{1}{2}(m-1) \geqq 56$, i.e., $m \geqq 113$. Since the number 113 is a prime number, the smallest sought number is $m=113$.

Another solution. The sum of all fractions that have denominator $m$, are not integers, and lie in the interval $(p, q)$, can also be determined as the difference between the sum of all fractions with denominator $m$ lying in the closed interval $\langle p, q\rangle$ and the sum of all natural numbers in this interval. For the considered difference $d$, we have

$$
d=\sum_{j=p m}^{q m} \frac{j}{m}-\sum_{j=p}^{q} j
$$

Both the numerator and the denominator in the considered difference can be determined as sums of terms of arithmetic sequences. For the sum of the first $n$ terms of an arithmetic sequence $\left(a_{i}\right)$, we use the known relation

$$
a_{1}+a_{2}+\ldots+a_{n}=\frac{1}{2} n\left(a_{1}+a_{n}\right) \text {. }
$$

For the sought difference $d$, we have:

$$
\begin{aligned}
d & =\frac{1}{2}(p+q)((q-p) m+1)-\frac{1}{2}(p+q)(q-p+1)= \\
& =\frac{1}{2}(p+q)[((q-p) m+1)-(q-p+1)]=\frac{1}{2}(m-1)\left(q^{2}-p^{2}\right)
\end{aligned}
$$

We will proceed further in the same way as in the previous solution method.