How to divide by 1000000 without resulting in: undefined reference to '__udivdi3'

I have a uint64_t which I need to divide by 1000000. I am working on an embedded system and just doing the division leads to this error:

undefined reference to '__udivdi3'

I can, however, do 32-bit divisions. I tried using multiplications and shifts, as well as some suggestions splitting and combining to use 32-bit divisions, but they all lead to accuracy issues or require 64-bit integers. As this is for a clock (converting into seconds) the inaccuracy ended up being a few hours, which is not acceptable.

How can I overcome this issue and split my 64-bit division into 32-bit or smaller divisions?

First you can shift right by 6 bits to divide by 64. The task that remains is then to divide by 15625. That fits into 16 bits, which makes it convenient to do simple long division with 16 bit "digits"

uint64_t divideBy1M(uint64_t n) {
    // divide by 64
    n >>= 6;
    uint64_t result = 0;
    
    uint32_t quot = ((uint32_t)(n>>32)) / 15625;
    result += ((uint64_t)quot) << 32;
    n -= ((uint64_t)(quot*15625)) << 32;

    quot = ((uint32_t)(n>>16)) / 15625;
    result += ((uint64_t)quot) << 16;
    n -= ((uint64_t)(quot*15625)) << 16;

    quot = ((uint32_t)n) / 15625;
    result += (uint64_t)quot;
    n -= (uint64_t)(quot*15625) << 16; //remainder
    return result;
}