#include <iostream>
#include <fstream>
#include <map>
#include <string.h>
#include <string>
#include <vector>
#include <set>
#include <algorithm>

using namespace std;

ifstream fin("inversmodular.in");
ofstream fout("inversmodular.out");


int rez=0;

void gcd(int a, int b, int &c, int &d)
{
    if (b==0)
    {
        c=1;
        d=0;
        rez=a;
        return;
    }

    int x,y;
    gcd(b,a%b,x,y);
    c=y;
    d=x - (a/b)*y;
}

int main()
{
    int n,a,c,d;
    fin>>n>>a;

    gcd(a,n,c,d);

    while (c<0) c+=n;

    fout<<c%n;

    return 0;
}