II. (50 points) Find the maximum value of a prime number $p$ with the following property: there exist two permutations (which can be the same) of $1, 2, \cdots, p$, $a_{1}, a_{2}, \cdots, a_{p}$ and $b_{1}, b_{2}, \cdots, b_{p}$, such that the remainders of $a_{1} b_{1}$, $a_{2} b_{2}, \cdots, a_{p} b_{p}$ when divided by $p$ are all distinct.
Lemma (Wilson's Theorem): For any prime $p$, we have $(p-1)! \equiv -1 \pmod{p}$.

Proof of the Lemma: When $p=2,3$, equation (1) is obviously true.
When $p>3$, we prove: For any $2 \leqslant k \leqslant p-2$, there must exist $k^{\prime}\left(2 \leqslant k^{\prime} \leqslant p-2, k^{\prime} \neq k\right)$, such that $k k^{\prime} \equiv 1 \pmod{p}$.
In fact, for $2 \leqslant k \leqslant p-2$, we have $(k, p)=1$.
Thus, $k, 2k, \cdots, pk$ form a complete residue system modulo $p$.
Therefore, there must exist $k^{\prime}\left(1 \leqslant k^{\prime} \leqslant p\right)$, such that $k k^{\prime} \equiv 1 \pmod{p}$.
Clearly, $k^{\prime} \neq p$, otherwise $k k^{\prime} \equiv 0 \pmod{p}$, which is a contradiction.
Moreover, if $k^{\prime}=1$, then by $k k^{\prime} \equiv 1 \pmod{p}$, we get $k \equiv 1 \pmod{p}$, which contradicts $2 \leqslant k \leqslant p-2$.

If $k^{\prime}=p-1$, then by $k(p-1) \equiv 1 \pmod{p}$, we get $-k \equiv 1 \pmod{p}$, which contradicts $2 \leqslant k \leqslant p-2$.

If $k^{\prime}=k$, by $k k^{\prime} \equiv 1 \pmod{p}$, we get $k^2 \equiv 1 \pmod{p}$. Therefore, $p \mid (k+1)(k-1)$, but $1 \leqslant k-1 \leqslant p-3$, which contradicts equation (2), so $p \leqslant 2$.
When $p=2$, let
$$
a_{1}=1, a_{2}=2, b_{1}=1, b_{2}=2.
$$

At this point, $a_{1} b_{1}=1=1 \pmod{2}$,
$$
a_{2} b_{2}=4 \equiv 0 \pmod{2}.
$$

Therefore, $p=2$ satisfies the condition. Hence, $p_{\max}=2$.