Mình nghĩ là như thế này, không biết chuẩn không.
Ta chỉ cần xét trường hợp $x\neq y$.
Giả sử $x>y$.
Đặt $x=yq+r(r,q\in\mathbb N^*; r<y)$.
Nếu $r=0$ thì $\gcd(x,y) = y$ nên bài toán hiển nhiên đúng.
Nếu $r>0$ thì $(a^y)^q.a^r\equiv (b^y)^q.b^r\pmod m$.
Do $(a,m)=(b,m)=1$ và $a^y\equiv b^y\pmod m$ nên $a^r\equiv b^r\pmod m$.
Lúc này, $\gcd(x,y)=\gcd(y,r)$ nên lặp lại liên tục, ta có bài toán đúng theo giải thuật Euclid.
mik ko hiểu cái đoạn triệt tiêu thành a^r đồng dư b^r mod m lắm