解释评估模块化作业？

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，就像你的老师说的那样。

您可以使用扩展的欧几里德算法计算一个数的模逆。我会留给你去解决这个问题。有很多地方可以查找扩展的欧几里德算法（可能包括您的教科书或教师给您的课堂笔记）。或者，如果您在使用代码时遇到问题，则可以回到此处并提出另一个问题。