import java.io.*;
import java.util.StringTokenizer;

class Pair {
    long x, y;
}

public class Main {
    public static void im(final long a, final long b, final Pair p) {
        if (b == 0) {
            p.x = 1;
            p.y = 0;
        } else {
            final Pair p0 = new Pair();
            im(b, a % b, p0);

            p.x = p0.y;
            p.y = p0.x - (a / b) * p0.y;
        }
    }

    public static void main(final String[] args) throws IOException {
        final MyScanner cin = new MyScanner("inversmodular.in");
        final PrintWriter cout = new PrintWriter("inversmodular.out");

        final long a = cin.nextInt();
        final long n = cin.nextInt();

        final Pair p = new Pair();
        im(a, n, p);
        if (p.x < 0) p.x = n + p.x % n;

        cout.print(p.x);
        cout.close();
    }

    private static class MyScanner {
        private final BufferedReader bufferedReader;
        private StringTokenizer stringTokenizer;

        MyScanner(final 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();
        }
    }
}