#include <iostream>
#include <fstream>

using namespace std;

// Functie pentru calculul inversului modular al lui A in raport cu N
int calculateModularInverse(int A, int N) {
    int r1 = N, r2 = A;
    int t1 = 0, t2 = 1;

    while (r2 > 0) {
        int q = r1 / r2;
        int temp = r2;
        r2 = r1 - q * r2;
        r1 = temp;
        temp = t2;
        t2 = t1 - q * t2;
        t1 = temp;
    }

    if (r1 == 1) {
        // Daca r1 = 1, atunci inversul modular exista
        // Asiguram ca rezultatul este pozitiv in intervalul [1, N-1]
        return (t1 + N) % N;
    }

    // In caz contrar, nu exista invers modular
    return -1;
}

int main() {
    int A, N;

    // Citim valorile A si N din fisierul de intrare
    ifstream inputFile("inversmodular.in");
    inputFile >> A >> N;
    inputFile.close();

    // Calculam inversul modular al lui A in raport cu N
    int result = calculateModularInverse(A, N);

    // Scriem rezultatul in fisierul de iesire
    ofstream outputFile("inversmodular.out");
    outputFile << result << endl;
    outputFile.close();

    return 0;
}