Search code examples
pythonmathmodulusarithmetic-expressions

Math question on solving modular equations

I have the following modular equation:

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)

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

I know that -28%1009 = 981, but what i don't know is how the author derived knowing to multiply by 3 to get an answer that creates the mod that gets the number. Any help here would be appreciated

The full formula is here, i know that this can be solved with EGCD, but i'm trying to understand how the author solved the solution the way he did:

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.

Ok based on the responses, i came up with this program which seems to verify the results:

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

result:

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
Solution

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

    This is simply division with remainder.

    Calculate 1009/327 and you get approximately 3.085626911. That tells you that 1009 = 3*327 + R, where the remainder R is less than 327.