solve modular congruence ax ≡ b (mod n)

mod.c

/*
* author: hiendv
* with the help of: locbq, lampt 
* email: [email protected]
* date: 05-11-2014
* compiler: gcc, g++
*/
#include <stdio.h>
#include <stdbool.h> // boolean support for C
int a,b,n,gcd;
int dvd[100],dvs[100],r[100],s[100];
int at,bt,nt,temp,i,x0;
int count = 0;
void import(bool dev){
	if(dev){
		a = 179;
		b = 669;
		n = 867;
	} else {
		printf("%s\n", "ax ≡ b (mod n)");
		printf("%s\n", "Input a b n");
		scanf("%d %d %d",&a, &b, &n);
	}
	at = a;
	bt = b;
	nt = n;
}
bool checkDivisible(){
	if(b % gcd != 0) return false; else return true;
}
void simplify(){
	if(at > nt){
		at = at % nt;
	}
}
void drawTable1(){
	printf("n\ta\tq\tr\n");
	while(nt % at >=0){
		printf("%d\t%d\t%d\t%d\n",nt,at,nt/at,nt % at);
		if(nt % at == 0){
			gcd = at;
			break;
		} else{
			dvd[count] = nt;
			dvs[count] = at;
			count++;
		}
		temp = nt;
		nt = at;
		at = temp % at;
	}
}
void makePositive(){
	while(x0 < 0) x0 = x0 + (n/gcd);
}
void x0Caculation(){
	printf("gcd = d = n*s + a*r");
	printf("\ndvd\ts\tdvs\tr\n");
	s[count-1] = 1;
	for(i = count-1;i>=0;i--){
		r[i] = (gcd - dvd[i]*s[i])/dvs[i];
		printf("%d\t%d\t%d\t%d\n",dvd[i], s[i], dvs[i], r[i]);
		s[i-1] = r[i];
	}
	if(a > 1){
		x0 = ((r[i+1]*b)/gcd) % n;
	} else {
		x0 = b;
	}
	makePositive();
	printf("\nx0 = r*b/d = %d*%d/%d = %d (mod %d)\n",r[i+1],b,gcd,x0,n/gcd);
}
void printResult(){
	printf("\nx = {");
	for(i = gcd ;i>0;i--){
		printf("%d ",x0);
		x0 = x0 + n / gcd;
	}
	printf("}\n");
}
void printGCD(){
	printf("\n%s: %d\n", "GCD", gcd);
}
main(){
	import(false);// {'dev': true} -> use default values and skip the import process;
	simplify();
	drawTable1();
	printGCD();
	if(!checkDivisible()){
		printf("Not divisible. No solution\n");
	} else {
		x0Caculation();
		printResult();
	}
}