【Analysis】From the perspective of combinations (graph theory).
For $k=0,1, \cdots, p-1$, define the graph $G_{k}$: its vertex set is $\{1,2, \cdots, p\}$, and vertices $i, j$ are connected by an edge if and only if $a_{i}+i k \equiv a_{j}+j k(\bmod p)$.
Notice that, for a given $i \neq j$, we have
$(i-j, p)=1$.
Thus, there exists a unique $k \in\{0,1, \cdots, p-1\}$ such that
$k(i-j) \equiv a_{j}-a_{i}(\bmod p)$.
Therefore, the graphs $G_{0}, G_{1}, \cdots, G_{p-1}$ have a total of $\mathrm{C}_{p}^{2}$ edges.
If $p$ is an odd prime, then by the pigeonhole principle, there must exist a graph $G_{k}$ with at most $\frac{1}{p} \mathrm{C}_{p}^{2}=\frac{p-1}{2}$ edges.

Since a connected graph with $n$ vertices has at least $n-1$ edges, the graph $G_{k}$ must have at least $p-\frac{1}{p} \mathrm{C}_{p}^{2}=\frac{p+1}{2}$ connected components.
Let $[x]$ denote the greatest integer not exceeding the real number $x$.
If $p=2$, then there must exist a graph $G_{k}$ with at most $\left[\frac{1}{2} \mathrm{C}_{2}^{2}\right]=0$ edges (i.e., no edges). Thus, the graph $G_{k}$ must have at least 2 connected components.

In summary, for any case, there exists a graph $G_{k}$ with at least 2 connected components, which indicates that there exists an integer $k$ such that $a_{1}+k, a_{2}+2 k, \cdots, a_{p}+p k$ have at least $\frac{p}{2}$ distinct remainders when divided by $p$.