#include <stdio.h>
#include <iostream>

using namespace std;

int divz[ 1000 ];
int nD;
long long step;
long long sol;

long long N,P;

long long nP( long long X ) {
	long long Y, add;
	long long nSt = 0;
	for ( int cfg = 1; cfg < (1<<nD); cfg++ ) {
		Y = 1; add = -1;
		for ( int j = 0; (1<<j) <= cfg; j++ ) 
			if ( (1<<j) & cfg ) {
				Y *= divz[j+1]; add = 0-add;
			}
		nSt += ( (long long) X/Y )*add;
	}
	return (X-nSt);
}

int main()
{
	freopen("frac.in","r",stdin);
	freopen("frac.out","w",stdout);

	scanf("%lld\n%lld\n", &N, &P );

	for ( int i = 2; i * i <= N; i++ )
		if ( (N % i) == 0 ) {
			divz[ ++nD ] = i;
			for ( ; !(N%i); N /= i );
		}

	if ( N-1 ) divz[ ++nD ] = N;
	step = ( 1LL<<61 );
	for ( sol = 0; step; step >>= 1 )
		if ( nP( sol + step ) < P )
			sol += step;
	printf("%lld\n", sol+1 );
	return 0;
}