#include <bits/stdc++.h>

using namespace std;

//firstly first, 30 de puncte

ifstream f("inversmodular.in");
ofstream g("inversmodular.out");

long long a, n;

int main()
{
    ios_base::sync_with_stdio(false);
    f>>a>>n;
    for (long long x=1; x<=n; x++){
        if ((long long)(a*x)%n==1){
            g<<x;
            return 0;
        }
    }
    return 0;
}