#include <iostream>

using std::cin;

using std::cout;

using std::endl;

int Euclid(int,int,int,int);

int main()
{
    int n,u;
    cout<<"please input n and u"<<endl;
    cin>>n;
    cin>>u;
    cout<<(Euclid(n,u,0,1) + n) % n<<endl;
    system("pause");
    return 0;

}
int  Euclid(int n, int u, int b1, int b2)
{

    int q; //商
    q = n / u;
    int r; //余数
    r = n % u;
    if(0 != r)
    {
        int t;//中间变量
        n = u;
        u = r;
        t = b2;
        b2 = b1 - q * b2;
        b1 = t;
        return Euclid(n,u,b1,b2);
    }
    else
    {
        if(1 != u)
            cout<<"Error"<<endl;
        else
            return b2;
    }
    return 0;
}   
注意：比如求13模35的逆元，须先输入35再输入13.本人只测试了这组数据。