#include <stdio.h>

long long N,i,A,nr,nrr;

void euclid(long long &x,long long &y, long long a, long long b)     
{     
    long long aux;
     if (b==0)     
         {
            x=1;
            y=0;
         }     
     else     
     {                
         euclid(x,y,b,a%b);   
         aux=x;   
         x=y;   
         y=aux-y*(a/b);   
     }   
}   


int main()
{
    freopen("inversmodular.in","r",stdin);
    scanf("%ld %ld", &A,&N);
    nr=0;
    nrr=0;
    euclid(nr,nrr,A,N);
    freopen("inversmodular.out","w",stdout);
    if (nr>0) printf("%ld", nr);
         else printf("%ld", A+nr%A);      
return 0;
}