Redaksiya

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

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

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

Example

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

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

Compute the answer: $x=(4\ast 8^{-1})mod13=(4\cdot 5)mod13=20mod13=7$.

Algorithm realization

The function powmod computes the value of $x^{n}modm$.

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}modn,x=a\cdot ymodn$.

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}modn,x=a\cdot ymodn$.

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

Print the answer.

print(x)