title: How to find gcd(a,b) % p efficiently where p is a prime?
body: <p>My approach is very simple:</p>
  
  <ul>
  <li><strong>First, Finding <code>gcd(a,b)</code> using Euclid<em>'s</em> Algorithm.</strong>  </li>
  <li><strong>Then taking out mod with <code>p=10^9+7</code></strong></li>
  </ul>
  
  <p>But I need an efficient way (just need the right track not code):</p>
  
  <p>Values of <code>a</code> and <code>b</code> could in between <code>1</code> to <strong><code>10^12</code></strong> whereas <code>p</code> is a <strong><code>prime 10^9+7</code></strong></p>