Can you prefetch the answers and use a lookup table? Instead of
c = a%b;
you could then try
c = table[a][b];
Some considerations to signature and tablesize have to be made. Depending on the overall usecase you could move this table to a higher level and remove more that just this single computation.
A custom implementation of modulo would use the definition of it
(a/b)*b + a%b == a; //true
a%b == a - (a/b)*b // true
Depending on the likely values for a and b you could try to optimize this.
Depending on your target hardware you could try to see if there is a speedy hardwaresolution that can solve this for a specific product. (see this)
There may be more solutions out there.