// algorithm from http://en.wikipedia.org/wiki/Least_common_multiple
func lcm(a, b uint64) uint64 {
    return (a / gcd(a, b)) * b
}

// copied from C in http://en.wikipedia.org/wiki/Binary_GCD_algorithm
func gcd(u, v uint64) uint64 {
    var shift uint

    switch {
    case u == 0:
        return v
    case v == 0:
        return u
    }

    for shift = 0; ((u | v) & 1) == 0; shift++ {
        u >>= 1
        v >>= 1
    }

    for (u & 1) == 0 {
        u >>= 1
    }

    for {
        for (v & 1) == 0 {
            v >>= 1
        }
        if u > v {
            t := v
            v = u
            u = t
        }
        v = v - u

        if v == 0 {
            break
        }
    }

    return u << shift
}