#include<bits/stdc++.h>

#define ll long long

using namespace std;

void Exgcd(ll a,ll b,ll &d, ll &x,ll &y)

{

    if(!b)

    {

        d=a;

        x=;

        y=;

    }

    else

    {

        Exgcd(b,a%b,d,x,y);

        int t=x;x=y;y=t-a/b*y;

    }

}

int main()

{

    ll a,b,d,x,y;

    scanf("%lld%lld",&a,&b);

    Exgcd(a,b,d,x,y);

    printf("%lld",(x%b+b)%b);

    return ;

}