PROGRAM MODMAT(INPUT,OUTPUT);                               
 (*LOESE GANZZAHLIGE GLEICHUNGSSYSTEME                    *)
 (*(S. DISKRETE MATHE 4.SEMESTER)                         *)
 LABEL 1;                                                   
 CONST N=2;M=3;                                             
 TYPE MATRIX=ARRAY[1..N,1..M] OF INTEGER;                   
      VEKTOR=ARRAY[1..N]OF INTEGER;                         
 VAR P:INTEGER;  (*LFD. MOD.*)                              
     I,J,K,PCOUNT:INTEGER;                                  
     A,R:MATRIX;                                            
     NEWP,LASTP,R1,R2:INTEGER;                              
     Y,YS:VEKTOR;                                           
                                                            
 FUNCTION NORMAL(X:INTEGER):INTEGER;                        
 (*LIEFERT REPRAESENTANTEN AUS [-(P-1)..(P-1)]            *)
 BEGIN NORMAL:=X MOD P END;                                 
                                                            
 FUNCTION PLUS(X,Y:INTEGER):INTEGER;                        
 BEGIN PLUS:=NORMAL(X+Y) END;                               
                                                            
 FUNCTION MAL(X,Y:INTEGER):INTEGER;                         
 BEGIN MAL:=NORMAL(X*Y) END;                                
 FUNCTION INV(A0,P:INTEGER):INTEGER;                        
 (*BERECHNE INVERSES ELEMENT ZU A0(MOD P) MIT HILFE DES   *)
 (*ERWEITERTEN EUKLIDISCHEN GGT-ALGORITHMUS               *)
  VAR X0,X1,A1,Q,R,S:INTEGER;                               
 BEGIN                                                      
  IF A0<0 THEN A0:=A0+P;                                    
  A1:=P;X0:=0;X1:=1;                                        
  Q:=A1 DIV A0;R:=A1-Q*A0;                                  
  WHILE R<>0 DO                                             
   BEGIN A1:=A0;A0:=R;S:=X1;X1:=X0-Q*X1;X0:=S;              
    Q:=A1 DIV A0;R:=A1-Q*A0                                 
   END;                                                     
  INV:=X1;                                                  
  (*ES GILT: 1=A0=GGT(A0,P)=X1*X+K*P                      *)
 END;                                                       
                                                            
 PROCEDURE PRINT(VAR R:MATRIX);                             
 VAR I,J:INTEGER;CH:CHAR;                                   
 BEGIN                                                      
  FOR I:=1 TO N DO                                          
  BEGIN                                                     
   FOR J:=1 TO M DO WRITE(R[I,J]:6);                        
   WRITELN                                                  
  END;                                                      
  WRITELN;READ(CH);                                         
 END;(*PRINT*)                                              
                                                            
 PROCEDURE SWAP(VAR X,Y:INTEGER);                           
  VAR S:INTEGER;                                            
 BEGIN S:=X;X:=Y;Y:=S END;                                  
                                                            
 PROCEDURE TRYAGAIN;                                        
  BEGIN                                                     
   WRITELN("*** NICHT REGULAER (MOD",P,")! ***");           
   GOTO 1                                                   
  END;                                                      
 PROCEDURE PROBE(VAR X:VEKTOR);                             
  VAR I:INTEGER;                                            
 BEGIN                                                      
  WRITELN("ERGEBNIS:");                                     
  FOR I:=1 TO N DO  WRITE(X[I]);                            
  WRITELN                                                   
 END;                                                       
                                                            
BEGIN                                                       
 A[1,1]:=101;A[1,2]:=-131;A[1,M]:=  30;                     
 A[2,1]:= 70;A[2,2]:=- 92;A[2,M]:=-100;                     
 PCOUNT:=1;                                                 
 WRITELN("AUSGANGSMATRIX:");PRINT(A);                       
 REPEAT                                                     
 1:WRITE("PRIMZAHL",PCOUNT,":");READLN(P);                  
   FOR I:=1 TO N DO                                         
    FOR J:=1 TO M DO R[I,J]:=NORMAL(A[I,J]);                
   WRITELN("NORMALISIERT:");PRINT(R);                       
   (*BILDE OBERE DREIECKSMATRIX DURCH ZEILENOPERATIONEN:  *)
   FOR I:= 1 TO N-1 DO                                      
   BEGIN K:=I;(*PIVOT SUCHEN:                             *)
    WHILE R[K,I]=0 DO                                       
     IF K<N THEN K:=K+1 ELSE TRYAGAIN;                      
    (*TAUSCHE EVTL. ZEILEN                                *)
    IF K<>I THEN FOR J:=1 TO M DO SWAP(R[K,J],R[I,J]);      
    (*ELIMINIERE R[I,J] FUER I<J<=N                       *)
    R1:=INV(R[I,I],P);                                      
    FOR J:=I+1 TO N DO                                      
     BEGIN R2:=MAL(R[J,I],R1);                              
      FOR K:=I+1 TO M DO                                    
       R[J,K]:=PLUS(R[J,K],-MAL(R2,R[I,K]));                
      R[J,I]:=0;                                            
     END;                                                   
    PRINT(R);                                               
   END;                                                     
   (*RUECKWAERTS EINSETZEN: (Y BESTIMMEN)                 *)
   FOR I:=N DOWNTO 1 DO                                     
   BEGIN R1:=R[I,M];                                        
    FOR J:=I+1 TO N DO                                      
     R1:=PLUS(R1,-MAL(R[I,J],Y[J]));                        
    Y[I]:=MAL(R1,INV(R[I,I],P));                            
   END;                                                     
   PROBE(Y);                                                
   (*LOESUNG ZUSAMMENSETZEN                               *)
   WRITELN("BILDE LOESUNG:");                               
   IF PCOUNT=1 THEN                                         
    BEGIN YS:=Y;LASTP:=P END                                
   ELSE                                                     
    BEGIN NEWP:=P; R2:=INV(LASTP,NEWP);R1:=INV(NEWP,LASTP); 
     P:=NEWP*LASTP;R2:=MAL(R2,LASTP)  ;R1:=MAL(R1,NEWP);    
     WRITELN("R=",R1:6,R2:6);                               
     FOR I:=1 TO N DO                                       
       YS[I]:=PLUS(MAL(R1,YS[I]),MAL(R2,Y[I]));             
     LASTP:=P;                                              
    END;                                                    
   PROBE(YS);                                               
   PCOUNT:=PCOUNT+1;                                        
 UNTIL FALSE;                                               
END.