import java.util.*;
import java.io.*;
class Pair {
long x, y;
}
public class Main {
public static Pair im(long a, long b) {
Pair pp = new Pair();
if (b == 0) {
pp.x = 1;
pp.y = 0;
} else {
Pair p0 = im(b, a % b);
pp.x = p0.y;
pp.y = p0.x - (a / b) * p0.y;
}
return pp;
}
public static void main(String[] args) throws IOException {
MyScanner cin = new MyScanner("inversmodular.in");
PrintWriter cout = new PrintWriter("inversmodular.out");
long a = cin.nextInt();
long n = cin.nextInt();
Pair p = im(a, n);
if (p.x < 0) p.x = n + p.x % n;
cout.print(p.x);
cout.close();
}
private static class MyScanner {
private BufferedReader bufferedReader;
private StringTokenizer stringTokenizer;
MyScanner(String filename) throws FileNotFoundException {
bufferedReader = new BufferedReader(new FileReader(filename));
}
private String next() throws IOException {
while (stringTokenizer == null || !stringTokenizer.hasMoreElements()) {
stringTokenizer = new StringTokenizer(bufferedReader.readLine());
}
return stringTokenizer.nextToken();
}
int nextInt() throws IOException {
return Integer.parseInt(next());
}
void close() throws IOException {
bufferedReader.close();
}
}
}