Euler was also the one to generalise the result to non-prime integers. He could have used the Chinese remainder theorem to do so but the first know use of it by western mathematicians was due to Gauss in 1801.

To be fair mathematics was really close for a really long time, but before that generalisation not all of the ingredients were there at the same place at the same time. It might well have been possible for the Chinese or Hindu-Arabic mathematicians to discover Fermat's theorem or perhaps even Lagrange's theorem (which is how I'd prove it from scratch if necessary), but as far as I can tell they did not.