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

uint64_t gcd(uint64_t a, uint64_t b, int64_t &x, int64_t &y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    
    int64_t x1, y1;
    uint64_t d = gcd(b, a % b, x1, y1);
    
    x = y1;
    y = x1 - y1 * (a / b);
    
    return d;
}

uint64_t solve(uint64_t a, uint64_t n) {
    int64_t x, y;

    uint64_t g = gcd(a, n, x, y);

    if (g != 1) {
        return -1;
    }

    while(x < 0){
        x += n;
    }
    
    return x % n;
}

int main(){
    freopen("inversmodular.in", "r", stdin);
    freopen("inversmodular.out", "w", stdout);
    
    uint64_t A, N;
    cin >> A >> N;
    
    uint64_t rezultat = solve(A, N);
    cout << rezultat << '\n';
    
    return 0;
}