#include <stdio.h>

//pinex
long long div[20];
long long f( long long num ){
	long long d, i, j, dm, con;
	//fprintf ( stdout, "2\n" );
	d=0;
	for( i = 1 ; i < 1 << (  div[19] ) ; i++ ){
		dm = 1;
		con=0;
		//fprintf ( stdout, "%d-\n", i );
		for( j = 0; j < div[19] ; j++ )
			if ( i & ( 1 << j ) ){
				dm *= div[ j ];
				con++;
			}
		if ( con % 2 == 0 )
			d = d - num / dm;
		else
			d = d + num / dm;
		//fprintf ( stdout, "%lld - %lld\n", i, dm);
	}
	//fprintf ( stdout, "%lld -- %lld\n", num, num-d);
	return num - d;
}

int main(){
	long long p, n, d, poz, pas;
	FILE *fi = fopen ( "frac.in" , "r" ), *fo = fopen ( "frac.out" , "w" );
	fscanf(fi, "%lld%lld", &n, &p);
	//fprintf( stdout, "%lld %lld", n, p );
	d=2;
	while ( d*d <= n ){
		if ( n%d == 0 ){
			div[div[19]]=d;
			div[19]++;
			while( n%d == 0 ) n/=d;
		}
		d++;
	}
	if( n != 1 ){
		div[div[19]]=n;
		div[19]++;
	}
	//fprintf ( stdout , "%d\n", div[19] );
	poz=0;
	for( pas = 1LL<<61 ; pas > 0 ; pas /= 2 ){
		if( f( poz + pas ) < p )
			poz += pas;
		//fprintf( stdout, "1\n" );
	}
	fprintf ( fo , "%lld", poz+1 );
	fclose(fi);
	fclose(fo);
	return 0;
}