Complexity of taking mod
Shoup (Section 3.3.5, Theorem 3.3, p. 62) gives a bound for computing the residue $r$ in time $O(n\log q)$ where $a = q\cdot p +r$ and $\log a = n$.

I guess that if $p$ and $a$ are both roughly $n$ bit numbers, then $q$ (and hence $\log q$) should be rather small, giving $O(n)$.

If $a$ is an $n$-bit number, and $p$ is relatively small, then the multiplication approach should be faster.