3. If $m+2019 n$ and $n+2019 m$ are divisible by $d$, then the number

$$
2019(m+2019 n)-(n+2019 m)=(2019^2-1) n
$$

is also divisible by $d$. If $n$ is divisible by $d$, and $m+2019 n$ is divisible by $d$, then $m$ is divisible by $d$ and the numbers $m$ and $n$ are not coprime. Therefore, $d$ divides the number

$$
2019^2-1=2018 \cdot 2020=2^3 \cdot 5 \cdot 101 \cdot 1009
$$

Thus, the smallest possible prime number is $d=101$. It remains to find coprime $m$ and $n$ for which it is realized. For example, $m=102, n=1$. Then

$$
\begin{gathered}
m+2019 n=102+2019=2121=21 \cdot 101 \text { and } \\
n+2019 m=1+2019 \cdot 102=205939=2039 \cdot 101 .
\end{gathered}
$$
Answer: $d_{\text {min }}=101$.