#include <bits/stdc++.h>
using namespace std;
ifstream cin("inversmodular.in");
ofstream cout("inversmodular.out");
int euclid_extins(int &x, int &y, int a, int b){
 
    if(b == 0){
        x = 1;
        y = 0;
        return a;
    }
    else{
        int x1 , y1;
        int g = euclid_extins(x1, y1, b, a%b);
 
        x = y1;
        y = x1 - y1 * (a / b);
        return g;
    }
}
int main(){
 int a, b;
  cin >> a >> b;
  int x, y;
 
  euclid_extins(x,y,a,b);
  if(x < 0)
    x += b;
 
    cout << x;
}