#include <iostream>
#include <fstream>
using namespace std;
ifstream fin("inversmodular.in");
ofstream fout("inversmodular.out");
int cmmdc(long long a,long long b)
{
    if(b==0)
        return a;
    else
        cmmdc(b,a%b);
}
void euclid(long long a,long long b,long long &x,long long &y,long long &d)
{
    if(b==0)
    {
        x=1;
        y=0;
        d=a;
    }
    else
    {
        long long x0,y0;
        euclid(b,a%b,x0,y0,d);
        cout<<x0<<" "<<y0<<endl;
        x=y0;
        y=x0-a/b*y0;

    }
}
long long a,b,n,c,x,i,y,t,d;
int main()
{

        fin>>a>>n;
        c=cmmdc(a,n);
        cout<<c<<endl;
        euclid(a,n,x,y,d);
        while(x<0)x+=n;
         fout<<x;




}