The modular inverse – Algorithms Practice Problem

Dividing is not defined in modular arithmetic. The inverse is what you multiply by instead.

What to build

A program that finds the modular inverse with the extended Euclidean algorithm.

Requirements

Find the number x from 1 to m - 1 with a × x leaving remainder 1 when divided by m.
Print none if no such number exists.
Use Euclid's method, not a loop over every x.

Input

One line with a and m.

Output

The inverse, or none.

Constraints

1 ≤ a < m ≤ 1,000,000,007, and m ≥ 2.

Example

Input:

3 11

Output:

Why it works

Extended Euclid writes the GCD as a × t + m × s. When the GCD is 1, taking the remainder by m removes the m × s part, which leaves a × t ≡ 1, so t is the inverse. It is the same O(log m) loop as the ordinary GCD.

Examples

Example 1 · Input

3 11

Expected output

Example 2 · Input

2 4

Expected output

none

Hints

Hint 1

The inverse exists exactly when `gcd(a, m)` is 1.

Hint 2

Extended Euclid keeps a coefficient `t` alongside each remainder, updated with the same quotient.

Hint 3

The final `t` may be negative. Add `m` to bring it into range.

Solution

Show one correct solution (try it yourself first)

#include <stdio.h>

int main(void) {
    long long a, m;
    scanf("%lld %lld", &a, &m);
    long long t = 0, newt = 1, r = m, newr = a;
    while (newr != 0) {
        long long q = r / newr, tmp;
        tmp = t - q * newt;
        t = newt;
        newt = tmp;
        tmp = r - q * newr;
        r = newr;
        newr = tmp;
    }
    if (r > 1) {
        printf("none\n");
        return 0;
    }
    if (t < 0) t += m;
    printf("%lld\n", t);
    return 0;
}

Lesson: Number algorithms →