package ro.infoarena.arhiva.educationala.modularinverse;

import java.io.*;
import java.util.Scanner;

public class Main {

    private static class Solution {
        public long x, y;

        public Solution(final long x, final long y) {
            this.x = x;
            this.y = y;
        }
    }

    private static Solution egcd(final long a, final long b) {
        if (b == 0)
            return new Solution(1, 0);
        final Solution temp = egcd(b, a % b);
        return new Solution(temp.y, temp.x + (a / b) * temp.y);

    }

    public static void main(final String[] args) throws IOException {
        final String input = "inversmodular.in";
        final String output = "inversmodular.out";
        try (final Scanner scanner = new Scanner(new BufferedReader(new FileReader(input)));
             final BufferedWriter printWriter = new BufferedWriter(new FileWriter(output))) {
            final long a;
            final long n;
            a = scanner.nextInt();
            n = scanner.nextInt();
            final Solution solution = egcd(a, n);
            while (solution.x < 0) solution.x += n;
            printWriter.write(String.valueOf(solution.x % n));
        }
    }
}