#include <bits/stdc++.h>
using namespace std;
int gcd(int a,int b, int&x1,int&y1){
if(b==0) {
x1=1; y1=0;
return a;
}
int x2, y2;
int g = gcd(b,a%b,x2,y2);
x1=y2;
y1=x2-(a/b)*y2;
return g;
}
int main() {
int a ,b,x,y;
cin>>a>>b;
cout<<gcd(a,a%b,x,y)<<endl;
return 0;
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CgppbnQgZ2NkKGludCBhLGludCBiLCBpbnQmeDEsaW50JnkxKXsKCWlmKGI9PTApIHsKCQl4MT0xOyB5MT0wOwoJCXJldHVybiBhOwoJfQkKCWludCB4MiwgeTI7CglpbnQgZyA9IGdjZChiLGElYix4Mix5Mik7Cgl4MT15MjsKCXkxPXgyLShhL2IpKnkyOwoJcmV0dXJuIGc7Cn0KCgppbnQgbWFpbigpIHsKCWludCBhICxiLHgseTsKCWNpbj4+YT4+YjsKCWNvdXQ8PGdjZChhLGElYix4LHkpPDxlbmRsOwoJcmV0dXJuIDA7Cn0=