title: Least common multiple modulo some p
body: <p>Suppose we have to find least common multiple (<code>lcm</code>) of numbers <code>a1 ... an</code>.</p>
  
  <p>To solve this we can use a recursive solution:</p>
  
  <p><code>lcm(a, b) = (a * b) / gcd(a, b)</code> where <code>gcd(a, b)</code> denotes greates common divisor of <code>a</code> and <code>b</code></p>
  
  <p><code>lcm(a1 ... an) = lcm(a1, lcm(a2 ... an))</code></p>
  
  <p><strong>The question is:</strong></p>
  
  <p>What if we are interested in <code>lcm(a1 ... an) mod p</code> where <code>p</code> is some <strong>prime</strong> number. <code>lcm(a1 ... an)</code> is too large to be stored in <code>int</code>.</p>