import java.math.*;

public class RSABreak {

	static BigInteger B_ZERO=BigInteger.valueOf(0);
	static BigInteger B_ONE=BigInteger.valueOf(1);
	static BigInteger B_TWO=BigInteger.valueOf(2);
	static BigInteger B_THREE=BigInteger.valueOf(3);
	static BigInteger B_FOUR=BigInteger.valueOf(4);
	static BigInteger B_FIVE=BigInteger.valueOf(5);
	static BigInteger B_SIX=BigInteger.valueOf(6);

	public static void main(String[] args) {
		BigInteger N;
    BigInteger d, e;
		BigInteger p, q;

		N=new BigInteger(args[0]);
		e=new BigInteger(args[1]);
		if (args.length != 2) {
			System.exit(1);
		}
//System.out.println("fact " + N + " = " + fact(N));
		p=fact(N);
		p=new BigInteger("2343864797");
		q=N.divide(p);
//System.out.println("fact " + N + " = " + p + "*"+q);
		d=euclid(p,q,e);
//System.out.println("euclid("+p+","+q+","+e+") = " + d);
System.out.println(d);

//System.out.println("sqrt " + N + " = " + bsqr(N));
//		System.exit(0);
		
/*		p=bsqr(N);
		q=N.divide(p);
	
		while (N.remainder(p).compareTo(B_ZERO) != 0) {
			while (fact(p).compareTo(B_ZERO) != 0) {
				//q=p.subtract(p.subtract(N.divide(p)));
				//if (p.compareTo(q) == 0) {
					q=q.subtract(B_TWO);
				//}
				p=q;
				// p=p.subtract(B_TWO);
			}
//System.out.println("p(near)=" + p);
		p=p.subtract(B_TWO);
	}
	//p=fact(N);
//System.out.println(N + " = " + p + "*" );
		q=N.divide(p);
		
//System.out.println(q + ", e=" + e + "\n");
*/
		System.exit(0);

	}
	static BigInteger primes[]=new BigInteger[Integer.MAX_VALUE/500];
	static int cur=0;

	static BigInteger fact (BigInteger in) {
		BigInteger xn,xn1,xi,insqr,i;
		insqr=bsqr(in);
		xn=insqr;
		xi=B_ZERO;
		i=B_ZERO;
		xn1=B_ZERO;
		while (xn.compareTo(xi) != 0) {
			xn1=xn.multiply(xn).add(insqr).remainder(in);
			i=i.add(B_ONE);
			if (i.remainder(B_TWO).compareTo(B_ZERO) == 0) {
				xi=xn;
			}
		}
		if (xn1.compareTo(xn) == 1) {
			xn=xn1.subtract(xn);
		} else {
			xn=xn.subtract(xn1);
		}
		return(gcd(in,xn));
	}
	static BigInteger fact1 (BigInteger in) {
		BigInteger i;
		BigInteger insqr,insqr4;
		int oldtime;
		int j;

		oldtime=(int)(System.currentTimeMillis() / 1000);
		if (in.remainder(B_TWO).equals(B_ZERO)) {
			return(B_TWO);
		}
		if (in.remainder(B_THREE).equals(B_ZERO)) {
			return(B_THREE);
		}
		if (in.remainder(B_FIVE).equals(B_ZERO)) {
			return(B_FIVE);
		}
		// max=(BigInteger)Math.sqrt(in);

//System.out.println("cur = " + cur);
		//primes=new BigInteger[Integer.MAX_VALUE/1000];
		//cur=0;
		primes[0]=B_THREE;

		insqr=bsqr(in);
		insqr4=bsqr(insqr);
//		System.out.println("insqr = " +insqr + ", insqr4 = " +insqr4);
		for (i=insqr.subtract(insqr.remainder(B_SIX)).add(B_ONE);i.compareTo(B_SIX) == 1; i=i.subtract(B_SIX)) {
//		for (i=B_SIX.add(B_ONE);i.compareTo(insqr) == -1; i=i.add(B_SIX)) {
//				System.out.println("i = " +i);
//			if ( (int)(System.currentTimeMillis() / 1000)-oldtime > 10){
//				oldtime=(int)(System.currentTimeMillis() / 1000);
//				System.out.println("testing " +i );
//			}

			if (in.remainder(i).compareTo(B_ZERO) == 0) {
//System.out.println("found primes i = " +i );
				return(i);
			}
			if (in.remainder(i.add(B_FOUR)).compareTo(B_ZERO) == 0) {
//System.out.println("found primes i = " +i );
				return(i.add(B_FOUR));
			}
		}
//System.out.println("no primes, i = " +i );

		return(B_ZERO);
	}
	static BigInteger bsqr (BigInteger in) {
		BigInteger guess1,guess2;
		BigInteger step;

		guess1=in.divide(B_TWO);
		guess2=in.divide(guess1);
		while ((B_TWO).compareTo(guess1.subtract(guess2).abs()) == -1) {
			if (guess2.compareTo(guess1) == 1) {
				guess1=guess2.subtract(guess2.subtract(guess1).divide(B_TWO));
			} else {
				guess1=guess2.add(guess1.subtract(guess2).divide(B_TWO));
			}
			guess2=in.divide(guess1);
		}
		return(guess1);
	}
// d that has the property e*d mod ((p-1) * (q-1)) = 1
	static BigInteger euclid (BigInteger p, BigInteger q, BigInteger e) {
		BigInteger d, r1, r2, r3, q2, q3,s1,s2,s3,t1,t2,t3;
		int i;
		BigInteger goal;

		goal=p.subtract(B_ONE).multiply(q.subtract(B_ONE));

		r1=goal;
		r2=e;
		s1=t2=B_ONE;
		s2=t1=B_ZERO;
		
		q2=r1.divide(r2);
		while (r2.compareTo(B_ONE) != 0) {
			r3=r1.remainder(r2);
			q3=r2.divide(r3);
			s3=s1.subtract(q2.multiply(s2));
			t3=t1.subtract(q2.multiply(t2));
			r1=r2;
			r2=r3;
			q2=q3;
			s1=s2;
			s2=s3;
			t1=t2;
			t2=t3;
//System.out.println(r2 + "	" + "	" + q2 + "	" + s2 + "	" + t2);
		}
		
		return(t2.add(goal).remainder(goal));
	}
	static BigInteger gcd (BigInteger p, BigInteger q) {
		BigInteger d, r1, r2, r3, q2, q3,s1,s2,s3,t1,t2,t3;
		int i;
		BigInteger goal;

		goal=p.subtract(B_ONE).multiply(q.subtract(B_ONE));

		r1=p;
		r2=q;
		
		q2=r1.divide(r2);
		while (r2.compareTo(B_ONE) != 0) {
			r3=r1.remainder(r2);
			q3=r2.divide(r3);
			r1=r2;
			r2=r3;
			q2=q3;
//System.out.println(r2 + "	" + "	" + q2 + "	" + s2 + "	" + t2);
		}
		
		return(r2);
	}

}