/**
 * Author: Andu Scheusan (not_andu)
 * Created: 08.11.2023 17:44:54
*/

#include <bits/stdc++.h>
#pragma GCC optimize("O3")

using namespace std;

#define INFILE "inversmodular.in"
#define OUTFILE "inversmodular.out"

#define all(x) (x).begin(), (x).end()
#define MP make_pair
#define F first
#define S second

typedef long long ll;

void euclid(int a, int b, int &x, int &y){
    if(!b){
        x = 1; y = 0;
    }
    else{
        
        int x0, y0;
        euclid(b, a % b, x0, y0);
        x = y0;
        y = x0 - (a / b) * y0;

    }
}

void solve(){

    int a, n; cin >> a >> n;
    int x, y;

    euclid(a, n, x, y);
    while(x < 0){
        x += n;
    }

    cout << x << '\n';

}

int main(){
    
    ios_base::sync_with_stdio(false);

    freopen(INFILE, "r", stdin);
    freopen(OUTFILE, "w", stdout);

    cin.tie(nullptr);
    cout.tie(nullptr);

    solve();

    return 0;
}