#Python, 160 146 130 bytes
def r(s):
n=str(eval(s));c=0
while n[1:]:exec("n=str(reduce(lambda a,b:a%sb,map(int,list(n))))"%"*+"["+" in s]);c+=1
return n,c
Will post an explanation soon.
Input is in the form 12+12 or 5*35 (with normal + and * signs), and assumes that those are the only two operators.
It can handle number inputs as large as your computer's memory allows.
I'm almost certainly confident that this can be further
EDIT: 16 30 bytes saved thanks to @Copper.