#include <iostream>
#include <fstream>
#include <vector>

typedef int signed long long isll;


isll const minn = 1LL;
isll const maxn = 12000000000LL;
isll const minp = 1LL;
isll const maxp = 100000000000000LL; // 10 ** 14

// 1 <= n <= 12,000,000,000 (12 miliarde)
bool
square_root2(isll n, isll & sr)
{ bool ok; ok = ((minn<=n) && (n<=maxn)); if(!ok) { return ok; }
  isll p; isll q; isll r; q = n; q >>= 2; p = 1; while(0<q) { q >>= 2; p <<= 1; }
  for(q = p >> 1; 0<q; q >>= 1) { r=(p+q); if((r*r)<=n) { p = r; } }
  sr = p; return true;
}

bool
gcd(isll a, isll b, isll & cmmdc)
{ bool ok; ok = ((0<a)&&(0<b)); if(!ok) { return ok; }
  isll r;
  while(0!=b)
  { r = a%b;
    a = b;
    b = r;
  }
  // no - throw
  cmmdc = a; return true;
}

class frac
{ private:
  isll a_n;
  isll a_p;
  std::vector<isll> a_prime_factors;
  int a_number_of_coprimes;
  isll a_ans;
  bool a_ok;
  bool count(isll a, isll b, isll & number);
  bool find_prime_factors_of_n();
  bool solve_correct();
  bool solve();
  bool write();
  bool read();
  bool process();
  public:
  frac();
  bool get_ok() const throw();
};

bool
frac::get_ok() const throw()
{ return a_ok; }

frac::frac()
: a_ok(process())
{ }

bool
frac::process()
{ bool ok; ok = read() &&
    solve() &&
    write();
  return ok;
}

bool
frac::read()
{ std::ifstream is("frac.in");
  isll n; isll p; is >> n >> p;
  bool ok; ok = ((minn<=n)&&(n<=maxn)) &&
    ((minp<=p)&&(p<=maxp)) &&
    (!is.fail());
  if(!ok) { return ok; }
  a_n = n; a_p = p; return true;
}

bool
frac::write()
{ std::ofstream os("frac.out");
  os << a_ans << std::endl;
  bool ok; ok = os.good(); if(!ok) { return ok; }
  os.close(); ok = os.good(); return ok;
}

bool
frac::solve()
{ bool ok; ok = find_prime_factors_of_n(); if(!ok) { return ok; }
  isll n; n = a_n; isll cmul; ok = count(1, n, cmul); if(!ok) { return ok; }
  isll ccop; ccop = ((n-1+1)-cmul); // count of numbers in set {1,...,n} that are coprime with n
  isll p; p = a_p; isll k; k = (p-1) / ccop; p = p % ccop; if(0==p) { p = ccop; } 
  isll a; isll b; a = 1; b = n; isll m;
  while(a<b)
  { m = (a+b)/2; ok = count(a, m, cmul); if(!ok) { return ok; }
    ccop = (m-a+1)-cmul; if(p<=ccop) { b = m; } else { p -= ccop; a = m+1; }
  }
  if(1==p)
  { isll d;
    ok = gcd(a, n, d); if(!ok) { return ok; }
    ok = (1==d); if(!ok) { return ok; }
    -- p;
  }
  ok = (0 == p); if(!ok) { return ok; }
  ok = (b==a); if(!ok) { return ok; }
  // no-throw
  a_ans = (k * n) + b; return true;
}

bool
frac::find_prime_factors_of_n()
{ isll n; n = a_n; isll n1; n1 = n;
  std::vector<isll> v;
  if(0 == (n&1))
  { v.push_back(2); do { n >>= 1; } while ((0==(n&1)) && (0<n)); }
  bool ok; isll r; ok = square_root2(n, r); if(!ok) { return ok; }
  ok = ((0<=r)&&(((r*r)<=n)&&(n<((r+1)*(r+1))))); if(!ok) { return ok; }
  isll f; f=3;
  while(r>=f)
  { if(0==(n%f))
    { v.push_back(f); do { n /= f; } while (0 == (n%f));
      ok = square_root2(n, r); if(!ok) { return ok; }
      ok = ((0<=r)&&(((r*r)<=n)&&(n<((r+1)*(r+1))))); if(!ok) { return ok; }
    }
    f += 2;
  }
  if(1<n)
  { v.push_back(n); }
  // no-throw
  a_prime_factors.swap(v); return true;
}

bool
frac::count(isll a, isll b, isll & number)
{ std::vector<isll> prime((1<<a_prime_factors.size()), 0);
  std::vector<isll> prod((1<<a_prime_factors.size()), 0);
  std::vector<isll>::size_type i1;
  std::vector<isll>::size_type i2; i2 = a_prime_factors.size();
  for(i1=0; i2>i1; ++i1)
  { prime[(1<<i1)] = a_prime_factors[i1]; }
  prod[0] = -1;
  std::vector<isll>::size_type t; t = prod.size();
  std::vector<isll>::size_type s; isll sum; sum = 0; isll inc;
  std::vector<isll>::size_type e; isll p; isll x0; isll x; isll a1; isll b1;
  for(s=1; t>s; ++s)
  { e = s&(-s); // compute lsb of s
    p = prime[e]; x0 = -p * prod[s^e];
    prod[s] = x0; if(0>x0) { x= -x0; } else { x = x0; } 
    a1 = a%x; if(0==a1) { a1 = a; } else { a1 = a+(x-a1); }
    b1 = b%x; if(0==b1) { b1 = b; } else { b1 = b-b1; }
    if(a1<=b1)
    { inc= 1+(b1-a1)/x;
      if   (0<x0) { sum += inc; }
      else        { sum -= inc; }
    }
  }
  // no-throw
  number = sum; return true;
}

bool
solve_frac()
{ frac f;
  bool ok; ok = f.get_ok();
  return ok;
}

bool
solve(int argc)
{ return solve_frac(); }

int
main(int argc, char * * argv)
{ int status;
  bool ok;
  try
  { ok = solve(argc);
    status = ( ok ? 0 : 1 );
  }
  catch ( ... )
  { status = 2; }
  return status;
}