#include <bits/stdc++.h>
using namespace std;
ifstream fin("inversmodular.in");
ofstream fout("inversmodular.out");
int n, a, b, c;
int gcd(int a, int b, int &x, int &y){

    if(b == 0){
        x = 1;
        y = 0;
        return a;
    }
    else{
        int x1 , y1;
        int g = gcd(b, a % b, x1, y1);

        x = y1;
        y = x1 - y1 * (a / b);
        return g;
    }
}
int main(){

  fin >> a >> b;
  int x, y;

  gcd(a, b, x, y);
  while(x < 0)
    x += b;

    fout << x;
}