> 我不擅长讲，只能举几个例子—
> 欧几里德扩展法举例：
> 22×□≡ 1 mod 31
> 	31＝1×22＋9	-1×22 ≡ 9   		     即  30×22≡ 9 mod 31
> 	22＝2×9＋4	22-2×(-1×22) ≡ 4 	     即    3×22≡ 4 mod 31
> 	 9＝2×4＋1	-1×22-2×(3×22) ≡ 1          即  24×22≡ 1 mod 31
> 
> 28×□≡ 1 mod 75
> 	75＝2×28＋19	-2×28≡19		  即 73×28≡19 mod 75
> 	28＝1×19＋9	28-1×(-2×28)≡9	           即   3×28≡  9 mod 75
> 	19＝2×9＋1	(-2×28)-2×(3×38)≡1       即67×28≡ 1 mod 75
> 
> 269×□≡ 1 mod 349
> 	349＝1×269＋80	    -1×269≡80                  即  -1×269
> 	269＝3×80＋29	   269-3×(-1×269)≡29   	      即  4×269
> 	  80＝2×29＋22	   (-1×269)-2×(4×269)≡22     即 -9×269
> 	  29＝1×22＋7	   (4×269)-1×(-9×269)≡7     即 13×269
> 	  22＝3×7＋1	   (-9×269)-3×(13×269)≡1    即-48×269 得 301

• Re:如果你不懂扩展欧几里德算法，我可以举个例子## (24) luoqunyan 2007-11-18 15:34:50