#include <algorithm>

 #include <iostream>

 #include <cstdio>

 using namespace std;

 long long a,b,x,y;

 void exgcd(long long a,long long b,long long &x,long long &y)

 {

     if(b==)

     {

         x=;y=;

         return ;

     }

     exgcd(b,a%b,x,y);

     long long temp=y;

     y=x-y*(a/b);

     x=temp;

 }

 int main()

 {

     //scanf("%I64d%I64d",&a,&b);

     cin>>a>>b;

     exgcd(a,b,x,y);

     if(x<)

         x+=(-x/b)*b;

     //printf("%I64d",x%b);

     cout<<x%b;

     return ;

 }