##
##  pptmod.pl
##
##  Perl script to generate HTML tables of primitive pythagorean triples
##  modulo a given prime
##
##  Fred Curtis (fred@f2.org) 18 Oct 2000
##

use strict;

if (scalar(@ARGV) != 1) {
  print STDERR "Usage: $0 <prime-modulus>\n";
  exit(1);
}
my $modulus = $ARGV[0];

my $modulus2 = int($modulus / 2);
my $found = { };

print <<END;
<TABLE BORDER="1">
  <TR>
    <TH><I>i</I><BR>
      (mod $modulus)</TH>
    <TH><I>j</I><BR>
      (mod $modulus)</TH>
    <TH><I>a</I>=<I>ij</I><BR>
      (mod $modulus)</TH>
    <TH>2<I>b</I>=(<I>j</I><SUP>2</SUP>-<I>i</I><SUP>2</SUP>)/2<BR>
      (mod $modulus)</TH>
    <TH>2<I>c</I>=(<I>j</I><SUP>2</SUP>+<I>i</I><SUP>2</SUP>)/2<BR>
      (mod $modulus)</TH>
  </TR>
END

my $i;
my $j;
for ($i = 0; $i < $modulus; $i++) {
  for ($j = 0; $j < $modulus; $j++) {
    print <<END;
  <TR>
    <TD ALIGN="Center">$i</TD>
    <TD ALIGN="Center">$j</TD>
END
    if ($i == 0 && $j == 0) {
      print <<END;
    <TD COLSPAN="3" ALIGN="Center">
      Invalid, <I>gcd</I>(<I>i</I>,<I>j</I>)=$modulus</TD>
END
    } else {
      my $a = ($i * $j) % $modulus;
      my $b2 = ($j * $j - $i * $i) % $modulus;
      $b2 = ($b2 + $modulus) % $modulus;
      my $c2 = ($j * $j + $i * $i) % $modulus;
      my $b = ($b2 % 2 == 0 ? $b2 / 2 : ($b2 + $modulus) / 2);
      my $c = ($c2 % 2 == 0 ? $c2 / 2 : ($c2 + $modulus) / 2);
      $found->{$a}{$b}{$c} = 1;
      print <<END;
    <TD ALIGN="Center">$a</TD>
    <TD ALIGN="Center">$b2 (<I>b</I>=$b)</TD>
    <TD ALIGN="Center">$c2 (<I>c</I>=$c)</TD>
END
    }
    print <<END;
  </TR>
END
  }
}
    print <<END;
</TABLE>
END

print <<END;
<TABLE BORDER="1">
<CAPTION>
  <U>Summary</U>: Possible<BR>
  values of <I>a</I>,<I>b</I>,<I>c</I> modulo $modulus
</CAPTION>
<TR>
  <TH><I>a</I><BR>
    (mod $modulus)</TH>
  <TH><I>b</I><BR>
    (mod $modulus)</TH>
  <TH><I>c</I><BR>
    (mod $modulus)</TH>
</TR>
END
{
  my $x;
  my $y;
  my $z;
  foreach $x (sort {$a<=>$b} keys %{$found}) {
    foreach $y (sort {$a<=>$b} keys %{$found->{$x}}) {
      foreach $z (sort {$a<=>$b} keys %{$found->{$x}{$y}}) {
        print <<END;
	<tr>
	<td align=center>$x</td>
	<td align=center>$y</td>
	<td align=center>$z</td>
	</tr>
END
      }
    }
  }
}
print <<END;
</TABLE>
END