#include <bits/stdc++.h>
#define int long long
using namespace std;

ofstream fout("inversmodular.out");

int t, a, b, c, d, x, y;

char c1;

bool GetInt(int &x){

    if(c1 == -1)

        return false;

    c1 = getchar();

    while(c1 == ' ')

        c1 = getchar();

    if(c1 == -1)

        return false;

    int sgn = 1;

    x = 0;

    if(c1 == '-')

        sgn = -1;

    else x = c1 - '0';

    c1 = getchar();

    while(isdigit(c1)){

        x = x * 10 + (c1 - '0');

        c1 = getchar();

    }

    x *= sgn;

    return true;

}

void modinv(int a, int b, int &d, int &x, int &y){

    if(b == 0)

        d = a, x = 1, y = 1;

    else{

        int x1, y1;

        modinv(b, a % b, d, x1, y1);

        x = y1;

        y = x1 - a / b * y1;

    }

}

int32_t main(){

    freopen("inversmodular.in", "r", stdin);

    GetInt(a), GetInt(b);

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

    while(x < 0)

        x += b;

    fout << x;

}