1 #include<iostream>
 2 #include<cstdio>
 3 using namespace std;
 4 
 5 int p,q,x,y;
 6 
 7 int exgcd(int a,int b,int &x,int &y){
 8     if(b==0){
 9         x=1; y=0;
10         return a;
11     }
12     int d=exgcd(b,a%b,x,y);
13     int t=x;
14     x=y;
15     y=t-(a/b)*y;
16     return d;
17 }
18 
19 int main(){
20     cin>>p>>q;
21     exgcd(p,q,x,y);
22     cout<<(x+q)%q<<endl;
23     return 0;
24 }