/*
    Keep It Simple!
*/
 
#include<stdio.h>
long long n,m;
void euclid(long long a,long long b, long long *d,long long *x, long long *y)
{
    if(!b)
    {
        *d=a;
        *x=1;
        *y=0;
    }
    else
    {
        long long x0,y0;
        euclid(b,a%b,d,&x0,&y0);
        *x = y0;
        *y = x0 - ( a/b ) * y0;
    }
}
 
int main()
{
    freopen("inversmodular.in","r",stdin);
    freopen("inversmodular.out","w",stdout);
    scanf("%lld%lld",&n,&m);
    long long d,x,y;
    euclid(n,m,&d,&x,&y);
    if ( x <= 0 )
        x = m + x%m;
    printf("%lld",x);
}