> Should something like the following go in the standard library, most likely in the math module?

I'm not keen. Granted that the math module has exceeded its original remit of "wrappers for libm", but even so, I'd prefer to try to limit it to a basic set of building blocks. For me, things like CRT and xgcd go beyond that.

I'd suggest that for now, the right place for this sort of thing would be a PyPI library for elementary number theory. That library could include probably primality testing, basic factoring, continued fractions, primitive root finding, and other elementary number theory topics.