Fixed version with a quick demonstration of the problem:

#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>

uint64_t gcm2( uint64_t max, uint64_t lcm ) {

    int b = __builtin_ctzl( lcm & 0xfff );
    lcm <<= ( 12 - b );
    return ( max / lcm ) * lcm;
}

uint64_t gcm(uint64_t max, uint64_t lcm)
{
    lcm <<= 12 - __builtin_ctzl(lcm | 0x1000);
    return max - (max % lcm);
}


int main(int argc, char *argv[])
{
    unsigned long max = 12345 << 10;
    while (argc-- > 1) {
        unsigned long v = strtoul(argv[argc], NULL, 10);

        printf("gcm2(%lu,%lu) = %lu\n", max, v, gcm2(max, v));
        printf("gcm(%lu,%lu) = %lu\n", max, v, gcm(max, v));
    }
    return 0;
}
[download]

$ ./a.out 12 77 4096
gcm2(12641280,4096) = 0
gcm(12641280,4096) = 12640256
gcm2(12641280,77) = 12615680
gcm(12641280,77) = 12615680
gcm2(12641280,12) = 12632064
gcm(12641280,12) = 12632064