#include <stdio.h>
#include <iostream>
#include <fstream>
#include <vector>
#include <array>
#include <algorithm>
#include <vector>
#include <stack>
#include <set>
#include <assert.h>
#include <queue>
#include <chrono>
#include <memory>
 
using LL = long long;
using ULL = int long long;
 
const std::string _problemName = "inversmodular";
 
namespace std {
std::ifstream fin(_problemName + ".in");
std::ofstream fout(_problemName + ".out");
}
 
#define USE_FILES
 
#ifdef USE_FILES
#define cin fin
#define cout fout
#endif

void extendedEuclid(int& x, int& y, int& d, int a, int b) {
    if (b == 0) {
        x = a;
        y = 0;
        d = a;
        return;
    }

    int x1, y1;
    extendedEuclid(x1, y1, d, b, a % b);

    x = y1;
    y = x1 - (a / b) * y1;
}

int modularInverse(int a, int n) {
    int x, y, d;
    
    extendedEuclid(x, y, d, a, n);

    if (d != 1) {
        throw std::runtime_error("nope");
    }

    if (x < 0) {
        x += ((-x + n - 1) / n) * n;
    }
    if (x >= n) {
        x -= (((x - n + 1) + (n - 1)) / n) * n;
    }
    
    return x;
}

int main() {

    int a, n;
    std::cin >> a >> n;

    std::cout << modularInverse(a, n) << '\n';

    return 0;
}