3.78 Find all prime numbers $p$ that satisfy the following condition: for any prime $q<p$, if $p=k q+r, 0 \leqslant r<q$, then there does not exist an integer $a>1$ such that $a^{2}$ divides $r$.
(China National Team Selection Test, 1999)
[Solution] Notice that $p=2, p=3=1 \times 2+1$,
$$
\begin{array}{l}
p=5=2 \times 2+1=1 \times 3+2, \\
p=7=2 \times 3+1=1 \times 5+2 .
\end{array}
$$

all satisfy the conditions required by the problem.
However,
$$
p=11=1 \times 7+4=1 \times 7+2^{2} .
$$
$p=11$ does not satisfy the conditions required by the problem.
Now consider the case where $p>11$.
Examine $p-r=k q, 0 \leqslant r<11$ and from $p>11$ we know
$$
r \neq 1,2,3,5,6,7,10,11,12
$$

Now we study $p-4, p-8, p-9$.
Since $p-4$ cannot have a prime factor greater than 3, by (1)
$$
p-4=3^{a}, a \geqslant 2 \text {. }
$$

Since $p$ is an odd prime, $p-9$ is even and has a prime factor of 2, and its prime factors do not exceed 7.
Since $p-9=3^{a}-5$, $p-9$ cannot have a prime factor of 5.
Therefore, $p-9$ can only have prime factors of 2 and 7.
Now consider the highest power of 2 that divides $p-9$.
$$
p-9=3^{a}-5 \equiv\left\{\begin{array}{l}
1 - 5 \\
3 - 5
\end{array} \equiv \left\{\begin{array}{l}
4 \\
6
\end{array} \quad(\bmod 8)\right.\right.
$$

Thus, $8 \nmid p-9$.
Therefore, $p-9$ has only two possibilities:
$p-9=2 \cdot 7^{b}$, or $p-9=2^{2} \cdot 7^{b}$.
If $p-9=2 \cdot 7^{b}$, then $3^{a}-5=2 \cdot 7^{b}$,

which means
$$
3^{a}=2\left(7^{b}+1\right)+3 .
$$

This leads to $0 \equiv 7 \equiv 1(\bmod 3)$, a contradiction.
Therefore, the only possibility is $p-9=4 \cdot 7^{b}$.
Or $\quad p-8=4 \cdot 7^{b}+1$.
Since $p-8$ does not have a prime factor greater than 7.
By $\quad 3 \mid p-4$ we get $3 \nmid p-8$.
By $7 \mid p-9$ we get $7 \nmid p-8$.
Thus, $p-8$ can only have the prime factor 5,
$$
p-8=5^{c}
$$

Therefore, from (2) and (3) we get $4 \cdot 7^{b}=5^{c}-1, b \geqslant 0, c \geqslant 1$.
If $b \geqslant 1$, consider the sequence
$$
\left\{5^{c}-1(\bmod 7)\right\}=\{4,3,5,1,2,0,4,3,5,1,2,0, \cdots\} \text {, }
$$

Thus, $c$ is a multiple of 6.
Let $c=2 c^{\prime}, c^{\prime} \geqslant 1$.
Then $4 \cdot 7^{b}=25^{c^{\prime}}-1$,
which means $24 \mid 4 \cdot 7^{b}$, which is impossible.
Therefore, $b \geqslant 1$ does not hold. Thus $b=0, c=1$,
Hence $p-8=4 \cdot 7^{0}+1$, which means $p=13$.
In summary, $p=2,3,5,7,13$.