#include <iostream>
#include <fstream>
#include <cmath>
#include <vector>
#include <queue>
#include <deque>
#include <list>
#include <ctime>
#include <string>
#include <algorithm>
using namespace std;
ifstream ff("inversmodular.in");
ofstream gg("inversmodular.out");

struct tuplu{ int a,b; tuplu(int a0=0, int b0=0){a=a0;b=b0;} };
tuplu operator-(tuplu a,tuplu b){ return tuplu(a.a-b.a, a.b-b.b); }
tuplu operator*(int q, tuplu a){ return tuplu(q*a.a, q*a.b); }


void gcd(int a, int b, tuplu& v){
    int q,r;
    tuplu va(1,0),vb(0,1),vr;
    while(b!=0){
        q=a/b;
        r=a%b;
        a=b;
        b=r;
        vr=va-q*vb;
        va=vb;
        vb=vr;
    }
    v=va;
}

int main(){
    int a,n;
    tuplu v;
    ff >> a >> n;
    gcd(a,n,v);
    if(v.a<0)v.a+=(v.a/n+1)*n;
    gg << v.a;
    return 0;
}