In the textbook that I am reading it is said:
Euclid’s algorithm can easily be formalized as a state machine. The set of states is $N^2$ and there is one transition rule:
$(x,y) --> (y, (rem(x,y))$
I don't quite understand what is $N$ here, and why it is $N^2$.
It’s $\Bbb N$, not $N$: $\Bbb N$ is the set of non-negative integers, so $\Bbb N^2$ is the set of ordered pairs of non-negative integers. Thus, this state machine is infinite. For each state $\langle m,n\rangle$, where $m$ and $n$ are non-negative integers, it has a transition to state $\langle n,\operatorname{rec}(m,n)\rangle$, where $\operatorname{rec}(m,n)$ is the remainder when $m$ is divided by $n$. For example, the only transition from $\langle 17,5\rangle$ is to $\langle 5,2\rangle$, since $17=3\cdot5+2$.