Finding Greatest Common Divisor of Two Integers Using Pulverizer

Pulverizer is a method similar to Euclead’s algorithm that finds the greatest common divisor (GCD) of two integers. It logs the calculations so that how such GCD can be achieved with linear combination of the two integers is also found.

Here is a simple example in C:

int pulverizer(long a, long b){
    long xa[] = {1,0};
    long xb[] = {0,1};
    
    while(a != b){
        if(a > b){
            a = a - b;
            xa[0] = xa[0] - xb[0];
            xa[1] = xa[1] - xb[1];
        }else{
            b = b - a;
            xb[0] = xb[0] - xa[0];
            xb[1] = xb[1] - xa[1];
        }
    }
    
    printf("GCD(a,b) = %ld; coefficients can be (%ld, %ld) or (%ld, %ld).\n", a, xa[0], xa[1], xb[0], xb[1]);
}

Pulverizer is very useful in finding the multiplicative inverse of an integer $$k$$ modulo a relatively prime number $$p$$. Consider the following:$$!\gcd(k,p) = 1$$ There exists a pair of integers $$(s,t)$$ such that $$!sp + tk = 1$$

Therefore, $$1-tk = sp \implies p | 1-tk \implies tk \equiv 1 \pmod{p}$$.

Alternatively, Fermat’s little theorem and its generalization, Euler’s theorem, can also be used to find the multiplicative inverse.