1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
53:
54:
55:
56:
57:
58:
59:
60:
61:

#include <iostream>

using namespace std;

int knuth(int r, int s)
{
    int v,u,q,temp,n;
    n=s;
    v=0;
    u=1;
    while(r!=0)
    {
        q=s/r;
        temp=s-q*r;
        s=r;
        r=temp;
        temp=v-q*r;
        v=u;
        u=temp;
    }
    if(v<0) v+=n;
    return v;
}

int euklid(int x, int b)
{
    int s,s2,t1,s1,t,t2,temp,g,r,y;
    s=s2=t1=0;
    s1=t=t2=1;
    y=b;
    while(temp!=0)
    {
        g=x/y;
        r=x%y;
        s=s1-g*s2;
        t=t1-g*t2;
        s1=s2;
        s2=s;
        t1=t2;
        t2=t;
        x=y;
        y=r;
        temp=x%y;
    }
    if (s<0) s+=b;
    return s;
}

int main()
{
    int r,s;
    cout << "x eingeben: ";
    cin >> r;
    cout << "n eingeben: ";
    cin >> s;
    cout << "Inverse laut Knuth: " << knuth(r,s) << endl;
    cout << "Inverse laut Euklid: " << euklid(r,s) << endl;
    return 0;
}