title: Modulo product when the divisor is greater than both large factors
body: <p>In my C++ code I have three <code>uint64_t</code>variables:</p>
  
  <pre><code>uint64_t a =  7940678747;
  uint64_t b = 59182917008;
  uint64_t c = 73624982323;
  </code></pre>
  
  <p>I need to find <code>(a * b) % c</code>. If I directly multiply <code>a</code> and <code>b</code>, it will cause overflow. However, I can't apply the formula <code>(a * b) % c = ((a % c) * (b % c)) % c</code>, because <code>c &gt; a, c &gt; b</code> and, consequently, <code>a % c = a</code>, <code>a % c = b</code> and I will end up multiplying <code>a</code> and <code>b</code> again, which again will result in overflow.</p>
  
  <p>How can I compute <code>(a * b) % c</code> for these values (and such cases in general) of the variables without overflow?</p>