(In reply to

Possible Solution by broll)

I don't get why only prime M need to be checked.

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.

*Edited on ***June 24, 2017, 1:54 pm**