Well, I found an elementary proof for the Euclidean theorem from here :
It was okay until I got stuck in $x*b=qx_0b+rb$ :
"Indeed, let $x\in E$. We have $x=qx_0+r$ for a unique pair $(q,r)\enspace (0\le r<x_0)$. As $p$ divides $xb$ and $x_ob$, $p$ divides $xb-qx_0b=rb$"
I need to be more rigorously, but I didn't understand why $p$ divides $xb-qx_0b=rb$
Since $p$ divides $xb$ and $x_0b$, there are integers $m$ and $n$ such that $xb=pm$ and $x_0b=pn$. Then
$$xb-qx_0b=pm-qpn=p(m-qn)\,,$$
where $m-qn$ is an integer, so $p$ divides $xb-qx_0b$.