/*
  Author:  Pate Williams (c) 1997

  Exercise I.3.1
  "Describe all of the solutions of the following
  congruences:

  (a) 3x = 4 mod 7;   (d) 27x = 25 mod 256;
  (b) 3x = 4 mod 12;  (e) 27x = 72 mod 900;
  (c) 9x = 12 mod 21; (f) 103x = 612 mod 676."
  -Neal Koblitz-
  See "A Course in Number Theory and Cryptography"
  by Neal Koblitz second edition page 24.
*/

#include <stdio.h>

long Extended_Euclidean(long b, long n)
{
  long b0 = b, n0 = n, t = 1, t0 = 0, temp, q, r;

  q = n0 / b0;
  r = n0 - q * b0;
  while (r > 0) {
    temp = t0 - q * t;
    if (temp >= 0) temp = temp % n;
    else temp = n - (- temp % n);
    t0 = t;
    t = temp;
    n0 = b0;
    b0 = r;
    q = n0 / b0;
    r = n0 - q * b0;
  }
  if (b0 != 1) return 0;
  else return t % n;
}

long gcd(long a, long b)
{
  long r;

  while (b > 0)
    r = a % b, a = b, b = r;
  return a;
}

int main(void)
{
  long a[6] = {3, 3, 9, 27, 27, 103};
  long b[6] = {4, 4, 12, 25, 72, 612};
  long m[6] = {7, 12, 21, 256, 900, 676};
  long ai, bi, d, mi, i, x;

  for (i = 0; i < 6; i++) {
    ai = a[i];
    bi = b[i];
    mi = m[i];
    d = gcd(ai, mi);
    if (d == 1) {
      ai = Extended_Euclidean(ai, mi);
      x = (ai * bi) % mi;
    }
    else {
      if (bi % d != 0) x = 0;
      else {
        ai = ai / d;
        bi = bi / d;
        mi = mi / d;
        ai = Extended_Euclidean(ai, mi);
        x = (ai * bi) % mi;
      }
    }
    if (x != 0)
      printf("x = %3ld + %3ldn, n an integer\n", x, mi);
    else
      printf("no solution exists\n");
  }
  return 0;
}