I've written remainder(x,y) in OCaml. Is there more efficient than O(n)?
I don't know OCaml, but I know enough similar languages that I think I can read that well enough to answer.  Still, take this with a grain of salt.  

That is tail recursive.  You either return a value, or return the result of a recursive call that depends only on its input parameters that are known at the time of the call.  

There is a more efficient algorithm.  Hint: repeated subtraction.  (That may not be the most efficient algorithm.)

You don't actually use the parameter n, you could just use x directly in the same way you use y directly.  The name rem isn't the most descriptive; remainder would be better, but that particular function is mostly known as mod or modulus.  

I would find this formatting more readable:

if i = n 
then acc 
else if acc+1 = y 
     then aux      0  (i+1) n 
     else aux (acc+1) (i+1) n