Suponga lo contrario. Entonces existe un primo p y un entero positivo k, tal que [tex]$m=p^{2k-1}a$[/tex] para cierto a y [tex]$p\nmid a$[/tex]. se tiene que [tex]$mn|m^2+n^2+m\implies m|n^2\implies p^{2k-1}a|n^2\implies p^k|n\implies n=p^kb$[/tex] para cierto b. Reemplazando m y n tenemos [tex]$p^{3k-1}ab|p^{4k-2}a^2+p^{2k}b^2+p^{2k-1}a\implies p^{2k}|p^{4k-2}a^2+p^{2k}b^2+p^{2k-1}a\implies p^{2k}|p^{2k-1}a$[/tex] lo cual es contradiccion.
