Modular division (Megoldási útmutató)

Since the number $n$ is prime, by Fermat's Little Theorem, the equality b^{n - 1}~mod~n = 1 holds for any $b$ where 1 \le b < n. This equality can be rewritten as (b \cdot b^{n - 2})~mod~n = 1, which implies that the multiplicative inverse of $b$ is y = b^{n - 2}~mod~n. Consequently, a~/~b~mod~n = a \cdot b^{-1}~mod~n = a \cdot y~mod~n.

The multiplicative inverse can also be found using the extended Euclidean algorithm. To do this, one needs to solve the congruence ax = 1~(mod~n). Consider the Diophantine equation

and find its particular solution (x_0, y_0) using the extended Euclidean algorithm. Taking the equation ax_0 + ny_0 = 1 modulo $n$, we get ax_0 = 1~(mod~n). If x_0 is negative, $n$ should be added to it. Thus, x_0 = a^{-1}~(mod~n) is the multiplicative inverse of $a$.

Example

Let’s consider the second sample. We need to compute 4~/~8~mod~13. To do this, we should solve the equation 8 \cdot x = 4~mod~13, from which it follows that x = (4 \cdot 8^{-1})~mod~13.

Since the number $13$ is prime, by Fermat's Little Theorem, it follows that 8^{12}~mod~13 = 1 or (8 \cdot 8^{11})~mod~13 = 1. Therefore, 8^{-1}~mod~13 = 8^{11}~mod~13 = 5.

Compute the answer: x = (4 * 8^{-1})~mod~13 = (4 \cdot 5)~mod~13 = 20~mod~13 = 7.

Algorithm realization

The function powmod computes the value of x^n~mod~m.

long long powmod(long long x, long long n, long long m)
{
  if (n == 0) return 1;
  if (n % 2 == 0) return powmod((x * x) % m, n / 2, m);
  return (x * powmod(x, n - 1, m)) % m;
}

The main part of the program. Read the input data.

scanf("%lld %lld %lld", &a, &b, &n);

Calculate the values y = b^{n-2}~mod~n, x = a \cdot y~mod~n.

y = powmod(b, n - 2, n);
x = (a * y) % n;

Print the answer.

printf("%lld\n", x);

Algorithm realization — the Extended Euclidean algorithm

#include <stdio.h> 

long long a, b, n, d, x, y, inv, res;

void gcdext(long long a, long long b, 
            long long &d, long long &x, long long &y)
{
  if (b == 0)
  {
    d = a; x = 1; y = 0;
    return;
  }

  gcdext(b, a % b, d, x, y);

  long long s = y;
  y = x - (a / b) * y;
  x = s;
}

int main(void)
{
  scanf("%lld %lld %lld", &a, &b, &n);
  // b * inv + n * y = 1
  gcdext(b, n, d, inv, y);
  if (inv < 0) inv += n;
  res = (a * inv) % n;
  printf("%lld\n", res);
  return 0;
}

Python realization

The main part of the program. Read the input data.

a, b, n = map(int, input().split())

Calculate the values y = b^{n-2}~mod~n, x = a \cdot y~mod~n.

y = pow(b, n - 2, n)
x = (a * y) % n

Print the answer.

print(x)