#include<stdio.h>
#include<iostream>
#include<fstream>
#include<algorithm>
using namespace std;
void fct(long long &a,long long &b,int x,int n)
{
    if(n==0)
    {
        a=1;
        b=0;
    }
    else
    {
        fct(a,b,n,x%n);
        long long aux=a;
        a=b;
        b=aux-a*(x/n);
    }
}
int main()
{
    ifstream si;
    si.open("inversmodular.in");
    ofstream so;
    so.open("inversmodular.out");
    int a,n;
    long long x=0,y=0;
    si>>a>>n;
    fct(x,y,a,n);
    if(x<=0)
    {
        x=n+x%n;
    }
    so<<x<<'\n';
}