#include <stdio.h>      
     
     
int A, N;
long long m;      
     
int euclid_extins(int a, int b,long long &x, long long &y)        
{        
     if (!b)  x=1, y=0;        
     else        
     {                   
         m=euclid_extins(b,a % b,x,y);      
         long long t=x;      
         x=y;      
         y=t-y*(a/b);      
     }     
     return m; 
}      
     
int main()      
{      
          
    freopen("inversmodular.in", "r", stdin);      
    freopen("inversmodular.out", "w", stdout);      
          
    long long a=0,b;      
          
    scanf("%d %d", &A, &N);      
    m=euclid_extins(A,N,a,b);      
     
    if (a <= 0) a = N + a%N;      
             
    printf("%lld\n", a);      
            
    return 0;      
}