Untitled

#include <stdio.h>

int gcd(int a, int b) { 
    if (b == 0)
        return a;
    return gcd(b, a % b);
}


int mod_inverse(int a, int m) {
    int t = 0;
    int new_t = 1;
    int r = m;
    int new_r = a;

    while (new_r != 0) {
        int quotient = r / new_r;

        
        int temp_t = t;
        t = new_t;
        new_t = temp_t - quotient * new_t;

       
        int temp_r = r;
        r = new_r;
        new_r = temp_r - quotient * new_r;
    }

    
    if (r > 1) {
        printf("Inverse does not exist.\n");
        return -1;  
    }

    
    if (t < 0)
        t = t + m;

    return t;
}

int main() {
    int a, m;

    printf("Enter the number (a): ");
    scanf("%d", &a);
    printf("Enter the modulus (m): ");
    scanf("%d", &m);

    
    if (gcd(a, m) != 1) {
        printf("No multiplicative inverse exists because gcd(%d, %d) != 1.\n", a, m);
        return 0;
    }

    
    int inverse = mod_inverse(a, m);
    
    if (inverse != -1) {
        printf("Multiplicative inverse of %d modulo %d is: %d\n", a, m, inverse);
    }

    return 0;
}