fork download
copy 
  1. program extended_euclid_algorithm;
  2. var
  3. x,b,a,m,tempx,y,tempy,c,d,q,r,inverse:integer;
  4. begin
  5. 	tempx:=1; 
  6. 	tempy:=0;
  7. 	c:=0; d:=1;
  8. 	readln(a,m);
  9. 	b:=m;
  10. 	if(m<0) then
  11. 	begin
  12. 		m:=-m;
  13. 		a:=-a;
  14. 	end;
  15. 	while(m<>0) do
  16. 	begin 
  17. 		x:=tempx; y:=tempy;
  18. 		tempx:=c; tempy:=d;
  19. 		q:= a div m;
  20. 		q:=-q;
  21. 		c:=q*c;
  22. 		d:=q*d;
  23. 		c:=c+x;
  24. 		d:=d+y;
  25. 		r:=a mod m;
  26. 		a:=m;
  27. 		m:=r;
  28. 	end;
  29. 	writeln('the values of x and y are',tempx,' ',tempy);
  30. 	writeln('the gcd is given by ',a);
  31. 	if(a = -1) then
  32. 	begin
  33. 		a:=-a;
  34. 	end;
  35. 	if(a<>1) then
  36. 	writeln('the modular inverese cannot be find')
  37. 	else
  38. 	begin
  39. 	if(tempx<0) then
  40. 	inverse:= (b+tempx) mod b
  41. 	else
  42. 	inverse:=tempx mod b;
  43. 	writeln('the inverse is given by ',inverse);
  44. 	end;
  45. end.
  46.  
stdin
copy 
120
23
compilation info 
Free Pascal Compiler version 2.2.0 [2009/11/16] for i386
Copyright (c) 1993-2007 by Florian Klaempfl
Target OS: Linux for i386
Compiling prog.pas
Linking prog
45 lines compiled, 0.0 sec
stdout
copy 
the values of x and y are-9 47
the gcd is given by 1
the inverse is given by 14
https://ideone.com/o24UJ
language:
Pascal (fpc 3.0.4)
created:
12 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!