解釋評估模塊化作業？

Question

我正在爲我的編程類工作一個python任務。該問題要求我們採取一些輸入，並以a/b模N的形式，將a/b模N返回爲0和n-1之間的整數。如果b具有可乘的逆模N

這裏是我做了什麼：例如，輸入>>> a = 3，b = 2，n = 7 接受輸入並評估3/2，然後評估1.5mod7

但是，這不是老師想要的答案。正確的答案是5.

我在想的是在範圍（1，n）中找到一個整數，使得* integer == 1 mod N.這就是我們想要的。然而，在我給出的所有測試案例中，只有這個例子以這種方式工作。下面是我知道一些答案是不確定的，我知道如何讓這些輸入正確的輸出

input1: 3,2,7 
input2: 14, 67, 88 
input3: 10, 3, 40 

out1:5 
out2:58 
out3:30 

的例子，

我完全失去了對如何做到這三個，讓他回答需要。

Answer 1

在正常的算術中，可以通過乘以逆來執行除法。例如，2的倒數是1/2，所以除以3可以乘以3乘以1/2。請注意，2和它的逆1/2乘以1，這總是正確的;這就是逆的定義。

模塊化算術不允許分割，所以你必須乘以逆。當工作模7時，由於2 * 4 = 8 = 1（模7），所以2的倒數是4。反相總是那個乘以時等於1的數字，就像在正常的算術中一樣。所以，除以3（模7），3乘以4（模7）。現在3 * 4 = 12 = 5（mod 7），所以結果是5，就像你的老師說的那樣。

您可以使用擴展的歐幾里德算法計算一個數的模逆。我會留給你去解決這個問題。有很多地方可以查找擴展的歐幾里德算法（可能包括您的教科書或教師給您的課堂筆記）。或者，如果您在使用代碼時遇到問題，則可以回到此處並提出另一個問題。