/*
  Author:  Pate Williams (c) 1997

  Exercise III.2.3
  "Find all solutions (x, y) modulo N, writing
  x any as nonnegative integers less than N.
  (a) | 1 4 | 1 mod 9 (b) | 1 4 | 1 mod 9
      | 5 7 | 1           | 5 8 | 1
  (c) | 1 4 | 1 mod 9 (d) | 1 4 | 0 mod 9
      | 5 8 | 2           | 5 8 | 0".
  -Neal Koblitz-
  See "A Course in Number Theory and Cryptography"
  by Neal Koblitz second edition page 77.
*/

#include <malloc.h>
#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;
}

void solve_1(long N, long **A, long *B)
{
  long a, b, x, y, count = 0;

  for (x = 0; x < N; x++) {
    for (y = 0; y < N; y++) {
      a = (A[0][0] * x + A[0][1] * y) % N;
      b = (A[1][0] * x + A[1][1] * y) % N;
      if (a == B[0] && b == B[1]) {
        count++;
        printf("(%2ld, %2ld)\n", x, y);
      }
    }
  }
  if (count == 0) printf("no solution\n");
}

void solve(long N, long **A, long *B)
{
  long d = (A[0][0] * A[1][1] - A[0][1] * A[1][0]) % N;
  long **C, x[2], i;

  if (d == 0) {
    solve_1(N, A, B);
    return;
  }
  d = Extended_Euclidean(d, N);
  if (d < 0) d += N;
  if (d == 0) {
    solve_1(N, A, B);
    return;
  }
  C = calloc(2, sizeof(long *));
  for (i = 0; i < 2; i++)
    C[i] = calloc(2, sizeof(long));
  C[0][0] = (d * A[1][1]) % N;
  C[1][1] = (d * A[0][0]) % N;
  C[0][1] = (- d * A[0][1]) % N;
  C[1][0] = (- d * A[1][0]) % N;
  x[0] = (C[0][0] * B[0] + C[0][1] * B[1]) % N;
  x[1] = (C[1][0] * B[0] + C[1][1] * B[1]) % N;
  if (x[0] < 0) x[0] += N;
  if (x[1] < 0) x[1] += N;
  for (i = 0; i < 2; i++) {
    x[i] = (C[i][0] * B[0] + C[i][1] * B[1]) % N;
    if (x[i] < 0) x[i] += N;
  }
  printf("(%2ld, %2ld)\n", x[0], x[1]);
}

int main(void)
{
  long A[4][2][2] = {{{1, 4}, {5, 7}},
                     {{1, 4}, {5, 8}},
                     {{1, 4}, {5, 8}},
                     {{1, 4}, {5, 8}}};
  long B[4][2] = {{1, 1}, {1, 1},
                  {1, 2}, {0, 0}};
   long N[4] = {9, 9, 9, 9}, **C, i, j, k;

  C = calloc(2, sizeof(long *));
  for (i = 0; i < 2; i++)
    C[i] = calloc(2, sizeof(long));
  for (i = 0; i < 4; i++) {
    for (j = 0; j < 2; j++)
      for (k = 0; k < 2; k++)
        C[j][k] = A[i][j][k];
    solve(N[i], C, B[i]);
  }
  return 0;
}