Time complexity of a modulo operation

I am trying to prove that if $p$ is a decimal number having $m$ digits, then $p \bmod q$ can be performed in time $O(m)$ (at least theoretically), if $q$ is a prime number. How do I go about this?

A related question is asked here, but it is w.r.t to MATLAB, but mine is a general one.

The relevant text, that I am referring: chapter 32 -String Matching, PP:991, "Introduction to Algorithms" 3rd edition Cormen et al.

Assuming (as Jesko does) that $q$ is a constant and not part of the input, the usual long-division algorithm you learn at school will do quite nicely. The algorithm is the following:

1. Compute multiples $q$, $2q$, $3q$, $4q$, $\dots$, $10q$. This takes constant time, as it's independent of $q$.

2. Say $q$ has $k$ digits. Start with the first $k$ digits of $p$. Call this string $s$.

3. Compare it against each of the $10$ multiples of $q$; whichever $cq$ is the largest one smaller than $s$, write down $c$ as a digit of answer, subtract $cq$ from $s$, and "bring down" the next digit of $p$. That is, set $s$ to be $(s - cq)$ concatenated with the next digit of $p$.

4. If $s < q$, then it's your answer, stop. Else, go back to step $3$ and repeat.

Here's an image from Wikipedia, for the example of $q = 37$.

I will assume that $q$ is not part of your input, but rather a constant. Then, Algorithm D in 4.3.1 of Knuth's book "The Art of Computer Programming" (Volume 2) performs any long division in $O(m)$ steps.