回答

mとnが互いに素ではなかったら、aはa+1の約数になるので問題文が破綻するからでは無いでしょうか?
実際にa,m,nに具体的な数を入れてみたら互いに素でないと証明出来ないことが分かると思います。

この回答にコメントする
疑問は解決しましたか?