#include<cstdio>
using namespace std;
int x,y;
int gcd(int a,int b,int &x,int &y){
    if(!b){
        x=1,y=0;
        return a;
    }
    int ret=gcd(b,a%b,x,y);
    int t=x;
    x=y;
    y=t-a/b*y;
    return ret;
} 
int a,b;
int main(){
    scanf("%d%d",&a,&b);
    gcd(a,b,x,y);
    printf("%d",(x+b)%b);
    
    
}