#include <stdio.h>
long long int euclid(long long int N, long long int M)
{
    long long int x = 1;
    while (((1LL * N % M) * (x % M)) % M != 1)
    {
        x++;
    }
    return x;
}
int main()
{
    long long int N = 0, M = 0;
    freopen("inversmodular.in", "r", stdin);
    freopen("inversmodular.out", "w", stdout);
    scanf("%lld %lld", &N, &M);
    printf("%lld",euclid(N,M));
    return 0;
}