Nice. Here's an Erlang version of your code, which I think reads even more like math:

  gcd(A, B) when B == 0 -> A;
  gcd(A, B) when A < B  -> gcd(B, A);
  gcd(A, B)             -> gcd(B, A rem B).

I also really appreciated the posting of more of Dijkstra's thoughts (from rer0tsaz) above, in particular this line struck a chord:

  When programming languages emerged, the "dynamic" nature of
  the assignment statement did not seem to fit too well into the
  "static" nature of traditional mathematics.
  

(Along those lines, Erlang's recasting of the equals sign as a pattern matching operator felt so natural when I learned how it worked.)

[Edit: zap redundant sentence.]