#include <stdio.h>
#include <stdlib.h>

const char iname[] = "inversmodular.in";
const char oname[] = "inversmodular.out";

void gcd(long long int *inv, long long int *aux, int n, int a)
{
    if(!a)
    {
        *inv = 1;
        *aux = 0;
    }
    else
    {
        gcd(inv, aux, a, n%a);
        long long int x = *inv;
        *inv = *aux;
        *aux = x - *aux * (n/a);
    }
}

int main()
{
    FILE *in = fopen(iname, "r");
    FILE *out = fopen(oname, "w");

    int a, n;
    fscanf(in, "%d %d", &a, &n);
    long long int inv, aux;

    gcd(&inv, &aux, a,n);

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

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