Take M=35 for example.  Fermat's little theorem does indeed show 3^35 mod 7 = 3 and 3^35 mod 7 = 3, but 3^35 mod 35 = 12.  Also 4^35 mod 5 = 4 and 4^35 mod 4 = 4, but 4^35 mod 35 = 9.

I think all that you proved is 7 is the only prime M that divides 3^M+4^M.

Before I hit an overflow, direct calculation finds M=1, 7, 49=7^2, 343=7^3, 2401=7^4, and 2653=7*379 are values that divide 3^M+4^M.  Going to the OEIS finds sequence A045584 which other than 1, are all multiples of 7.