#include <stdio.h>
#include <vector>

const int op[] = { -1, 1 };

std::vector<long long> kkt;
int N;

long long Val( long long A ) {
	long long sol = 0;
	for( int i = 0; i < N; i++ )
		sol += A / kkt[ i ];

	return A - sol;
}

int main()
{
	int q;
	long long x, A, P;
	FILE *fin = fopen( "frac.in", "r" );

	fscanf( fin, "%lld %lld", &x, &P );

	{
		std::vector<long long> fact;
		if( !( x & 1LL ) ) {
			while( !( x & 1LL ) )
				x >>= 1LL;
			fact.push_back( 2 );
		}
		for( int i = 3; ( long long )i * i <= x; i += 2 )
			if( x % i == 0 ) {
				while( x % i == 0 )
					x /= i;
	 
				fact.push_back( ( long long )i );
			}

		if( x > 1 )
			fact.push_back( x );

		{
			long long val;
			long long rez = 0;
			int n = fact.size();
			int right = ( 1 << n ), cate;
			for( int i = 1; i < right; i++ ) {
				val = 1LL;
				cate = 0;
				for( int j = 0; j < n; j++ )
					if( ( i >> j ) & 1 )
						val *= fact[ j ], ++cate;
				kkt.push_back( op[ cate & 1 ] * val );
			}
			N = kkt.size();
		}

		fact.clear();
	}

	long long left = 0, sol = 0;
	long long right = ( 1LL << 61 );
	while( left <= right ) {
		long long med = ( left + right ) >> 1;
		//printf( "%lld %lld\n", med, Val( med ) );
		if( Val( med ) >= P ) {
			right = med - 1;
			sol = med;
		} else left = med + 1;
	}

	FILE *fout = fopen( "frac.out", "w" );

	fprintf( fout, "%lld\n", sol );

	fclose( fin );
	fclose( fout );
 	return 0;
}