#include <bits/stdc++.h>

using namespace std;

FILE *F=fopen("inversmodular.in", "r"), *G=fopen("inversmodular.out", "w");

int n, a;
long long inv, ins;

void gcd(long long &x, long long &y, int a, int b)
{
    if(!b)
    {
        x = 1; y = 0;
        return;
    }
    gcd(x, y, b, a%b);
    long long x1;
    x1 = x;
    x = y;
    y = x1 - y*(a/b);
}

int main()
{
    fscanf(F, "%d %d ", &a, &n);
    gcd(inv, ins, a, n);

    while(inv <= 0) inv = n+inv%n;

    fprintf(G, "%lld", inv);
    return 0;
}