sec numerical algorithms divides then bk for some integer solcf (nmlcf ( mnlcf (mn mlcf (mnnowfor any value there exists and such that km where > from the definition of the mod functionwe can derive the fact that bn/mcm mod since the lcf is factor of both and mand since km lthe lcf must therefore be factor of both km and land also the largest common factor of each of these terms as consequencelcf (nmlcf (mllcf (mn mod mthis observation leads to simple algorithm we will assume that > at each iteration we replace with and with mod until we have driven to zero int lcf(int nint mif ( = return nreturn lcf(mn )to determine how expensive this algorithm iswe need to know how much progress we are making at each step note that after two iterationswe have replaced with mod so the key question becomeshow big is mod relative to nn > / > bn/mc / mbn/mc / / mbn/mc mod / mod thusfunction lcf will halve its first parameter in no more than iterations the total cost is then (log