#include <iostream>
#include <stdio.h>
using namespace std;
int x,y,d;

FILE *fin, *fout;

void euclidrecursiv(int a, int b, int &d, int &x, int &y) {
  if (b == 0) {
    d = a;
    x = 1;
    y = 0;
    return;
  }
 // else {
    int x1,y1;
    euclidrecursiv(b, a % b, d, x1, y1);
    x = y1;
    y = x1 - (a / b) * y1;
  //}
}

int main() {

int n,i,a, b, c;

fin = fopen( "inversmodular.in", "r" );
fout = fopen( "inversmodular.out", "w" );

fscanf(fin,"%d %d", &a, &b);
euclidrecursiv(a, b, d, x, y);
while(x<0) x=x+b;

fprintf(fout,"%d",x);

fclose( fin );
fclose( fout );


    return 0;
}