/*
  Author:  Pate Williams (c) 1997

  Exercise III.2.4
  "Find all solutions (x, y) modulo N, writing
  x any as nonnegative integers less than N.
  (a) | 17 11 | 7 mod 29 (b) | 17 11 | 0 mod 29
      | 13 10 | 1            | 13 10 | 0
  (c) |  9 10 | 0 mod 29 (d) |  9 20 | 10 mod 29
      | 16 13 | 0            | 16 13 | 21
  (e) |  9 20 | 1 mod 29
      | 16 13 | 2."
  -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[5][2][2] = {{{17, 11}, {13, 10}},
                     {{17, 11}, {13, 10}},
                     {{9, 20}, {16, 13}},
                     {{9, 20}, {16, 13}},
                     {{9, 20}, {16, 13}}};
  long B[5][2] = {{7, 8}, {0, 0},
                  {0, 0}, {10, 21}, {1, 2}};
   long N[5] = {29, 29, 29, 29, 29}, **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 < 5; 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;
}