title: Modular inverse calculation stuck
body: <p>Here is my code so far:</p>
  
  <pre><code>def mod_div(a, b, n): 
  
  if gcd(b,n) != 1:
      return 'Undefined'    
  
  for x in range(1, n):
          if b*x%n == a%n:      
              return x   
  </code></pre>
  
  <p>this code takes the function gcd() which I made and returns the gcd, which i then use to calculate the inverse.  I did a search of the questions, and none of them seem to be giving me the correct answer.  </p>
  
  <p>My problem is this: when I do div_mod(3,2,7), the code returns 5, as it should.  However, when I do it for large numbers, such as n > 10000, it takes very long for the solution to compute because of the iteration through n to find the correct number.</p>
  
  <p>I tried looking at the other questions, and in their answers, they all have a similar thing, but instead of going for i in n, they all return x%n if gcd != 1.
  this does not help me,and it does not give the right answer.</p>
  
  <p>For example. if I use a=12, b = 3 and n= 11 it should return 4,but all the functions I found except for mine all return 1.</p>
  
  <p>I want to know if thereis a more efficient way to use eulids extended theorem other than testing each n, and hoping one works.</p>