关于求解模方程的数学问题

Question

我有以下mod元方程：

327≡ ℎ*327*327* ≡ ℎ*327 ≡ 1 (mod 1009) and so

 ≡ ℎ*327x ≡ ℎ*1 ≡ ℎ (mod 1009).

So I have to find out what ℎ is.

3*327=981≡-28(mod1009)

我不明白这里的3是怎么推导出来的，你用什么公式求3的

我知道 -28%1009 = 981，但我不知道作者是如何推导出知道乘以 3 以获得创建 mod 的答案的。如有任何帮助，我们将不胜感激

完整的公式在这里，我知道这可以用 EGCD 解决，但我想了解作者是如何按照他的方式解决问题的：

The question:

In [1505]: (327*327*108)%1009                                                                                                                                 
Out[1505]: 327
Only 108 (as far as i know( will return 327. So the equation is:

(327*327*x)%1009 = 327.  What is the quickest way to solve for this step by step. 
 ( What i don't understand is how the author solved for the 3 here in the step listed below ( 3*327 =981 ≡−28 (mod 1009) )

The Answer ( which worked )
gcd(327,1009)=1 so there is an ℎ so that 327∗ℎ≡1(mod1009) so if 327*327*≡327(mod1009) then

327≡ℎ*327*327*≡ℎ*327≡1(mod1009) and so

≡ℎ*327≡ℎ*1≡ℎ(mod1009).

So I have to find out what ℎ is.

3 * 327 = 981 ≡ −28 (mod 1009)

327=28 * 12 − 9 so

327≡(−3 * 327) * 12 − 9 ( mod 1009 )

378 * 327≡−9 (mod 1009)

28=3 * 9 + 1

-3 * 327 ≡ 3 * (-37 * 327)+1 (mod 1009)

108* 327≡1 (mod 1009)

So ℎ≡108 and ≡108 (mod 1009).

=====

And indeed 108* 327 *327=35316 *327= (1009 *35+1) *327=1009 *(35 *327)+327.

好的，根据回复，我想出了这个似乎验证了结果的程序：

def getmod4(A, N):
  multiplier = N//A
  a = A * multiplier
  b = -(N - a)
  va = b%N
  assert va == a

  # or, the next e,d can be done by a // b ??
  e = a // b #math.gcd((va|1)-1, (b|1)-1)
  #f = -(va//e)

  c = math.gcd((A|1)-1, (b|1)-1)
  c = abs(b)//c - c

  d = abs(b) * c - A

  assert ((-multiplier * A) * c - d)%N == A

  print(f"Equation: {abs(b)} * {c} - {d}:  {abs(b) * c - d}") 
  print(f"Verification: ((-{multiplier}*{A}) * {c} - {d})%{N} = {((-multiplier*A) * c - d)%N}")
  return abs(b) * c - d

结果：

In [3079]: getmod4(327,1009)                                                                                                                                  
Equation: 28 * 12 - 9:  327
Verification: ((-3*327) * 12 - 9)%1009 = 327
Out[3079]: 327

In [3081]: getmod4(261,10099)                                                                                                                                 
Equation: 181 * -20 - -3881:  261
Verification: ((-38*261) * -20 - -3881)%10099 = 261
Out[3081]: 261

Answer 1

What i don't understand is how the 3 is derived here, by what formula do you use to find the 3.

这简直就是division with remainder.

计算 1009/327 得到大约 3.085626911。这告诉你 1009 = 3*327 + R，其中余数 R 小于 327。

关于求解模方程的数学问题

Math question on solving modular equations

python

math

modulus

arithmetic-expressions