home *** CD-ROM | disk | FTP | other *** search
/ Skunkware 5 / Skunkware 5.iso / lib / calc / sumsq.cal < prev    next >
Encoding:
Text File  |  1995-07-17  |  869 b   |  45 lines
  1. /*
  2.  * Copyright (c) 1993 David I. Bell
  3.  * Permission is granted to use, distribute, or modify this source,
  4.  * provided that this copyright notice remains intact.
  5.  *
  6.  * Determine the unique two positive integers whose squares sum to the
  7.  * specified prime.  This is always possible for all primes of the form
  8.  * 4N+1, and always impossible for primes of the form 4N-1.
  9.  */
  10.  
  11. define ss(p)
  12. {
  13.     local a, b, i, p4;
  14.  
  15.     if (p == 2) {
  16.         print "1^2 + 1^2 = 2";
  17.         return;
  18.     }
  19.     if ((p % 4) != 1) {
  20.         print p, "is not of the form 4N+1";
  21.         return;
  22.     }
  23.     if (!ptest(p, min(p-2, 10))) {
  24.         print p, "is not a prime";
  25.         return;
  26.     }
  27.     p4 = (p - 1) / 4;
  28.     i = 2;
  29.     do {
  30.         a = pmod(i++, p4, p);
  31.     } while ((a^2 % p) == 1);
  32.     b = p;
  33.     while (b^2 > p) {
  34.         i = b % a;
  35.         b = a;
  36.         a = i;
  37.     }
  38.     print a : "^2 +" , b : "^2 =" , a^2 + b^2;
  39. }
  40.  
  41. global lib_debug;
  42. if (lib_debug >= 0) {
  43.     print "ss(p) defined";
  44. }
  45.