#Python, 160 146 129 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 31 bytes saved thanks to @Copper.

Python, 160 146 129 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 31 bytes saved thanks to @Copper.

#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.

#Python, 160 146 129 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 31 bytes saved thanks to @Copper.

#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.

#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.