CRT in C

CINTA

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
// s1 s2 a
// t1 t2 b
void egcd(int *a,int *b,int *s1,int *s2,int *t1,int *t2){
    printf("%d %d %d\n",*s1,*s2,*a);
    printf("%d %d %d\n\n",*t1,*t2,*b);
    if(*b == 0)
        return ;
    int divisor = (*a) / (*b);
    *s1 -= (divisor * (*t1));
    *s2 -= (divisor * (*t2));
    *a = (*a) % (*b);
    egcd(b,a,t1,t2,s1,s2);
}
// Calculate the inverse of M/mi mod mi
int GetInverse(int Mi,int mi){
    int s1 = 1;
    int s2 = 0;
    int t1 = 0;
    int t2 = 1;
    int MiTemp = Mi;
    int miTemp = mi;
    egcd(&MiTemp,&miTemp,&s1,&s2,&t1,&t2);
    if(MiTemp == 0){
        printf("%d * %d + %d * %d = 1\n",Mi,t1,mi,t2);
        if(t1 < 0)
            return mi + t1;
        return t1;
    }
    if(miTemp == 0)
        printf("%d * %d + %d * %d = 1\n",Mi,s1,mi,s2);
        if(s1 < 0)
            return mi + s1;
        return s1;
    return 1;
}
int main(){
    int equations;
    scanf("%d",&equations);
    int res[equations];
    int m[equations];
    int M = 1;
    // read all the mi and calculate M
    for(int i = 0;i < equations;i++){
        scanf("%d %d",&res[i],&m[i]);
        M *= m[i];
    }
    // we can not store inverse as well
    int inverse[equations];
    int sum = 0;
    int mi = 0;
    printf("M = %d\n",M);
    for(int i = 0;i < equations;i++){
        mi = M / m[i];
        // use GetInverse to get the inverse of Mi mod m[i]
        inverse[i] = GetInverse(mi,m[i]);
        printf("a[%d] = %d, bi = %d, bi-1 = %d\n\n",i,res[i],m[i],inverse[i]);
        sum += (res[i] * mi * inverse[i]);
    }
    int x = sum % M;
    printf("x = %d",x);
    return 0;
}