#include <fstream>
#include <algorithm>
#include <string.h>
#include <math.h>

using namespace std;
typedef long long ll;
ll limit = 110000;

int pfact = 0;
ll prim[16];
ll prod[(1<<12) + 5];
int sign_prod[(1<<12) + 5];

ll fun(ll x) // intoarce numarul de numere mai mici ca x care-s coprime cu N
{
    ll ret = 0;
    for (int n = 0; n < (1 << pfact); n++)
        ret += sign_prod[n] * (x / prod[n]);

    return ret;
}

void build_prod()
{
    for (int n = 0; n < (1 << pfact); n++)
    {
        prod[n] = 1;
        int cnt = 0;
        for (int j = 0; j < pfact; j++)
            if (n & (1 << j))
            {
                prod[n] *= prim[j];
                cnt++;
            }
        if (cnt % 2) sign_prod[n] = -1;
        else sign_prod[n] = 1;
    }
}

ll binary (ll low, ll high, ll val)
{
    ll mid, tmp;
    while (low < high)
    {
        mid = low + (high - low) / 2;
        tmp = fun(mid);
        if (tmp < val) low = mid + 1;
        else high = mid;
    }
    return low;
}

int main()
{
    ifstream f ("frac.in");
    ofstream g ("frac.out");

    ll N, n, eulerphi, P;
    f >> N >> P;
    n = eulerphi = N;

    if (N == 1)
    {
        g << P << '\n';
        return 0;
    }

    // factorizeaza N;
    if (N % 2 == 0) {
        prim[pfact] = 2;
        while (N % 2 == 0)
            N /= 2;
        pfact++;
    }

    for (ll p = 3; p*p <= N && p < limit; p += 2)
    {
        if (N % p == 0)
        {
            prim[pfact] = p;
            while (N % p == 0)
                N /= p;
            pfact++;
        }
    }

    if (N > 1)
    {
        prim[pfact] = N;
        pfact++;
    }

    // calculeaza eulerphi
    for (int i = 0; i < pfact; i++)
    {
        eulerphi /= prim[i];
        eulerphi *= prim[i] - 1;
    }
//    g << "N = " << n << '\n';
//    g << "P = " << P << '\n';
//    g << "phi(N) = " << eulerphi << '\n';
    
    ll answer = (P / eulerphi) * n;
    ll target = P % eulerphi;
    if (target == 0)
    {
        target += eulerphi;
        answer -= n;
    }

//g << answer << '\t' << target << '\n';
    build_prod();

    answer += binary(1, n, target);
    g << answer << '\n';

    return 0;
}