Hay una solución curiosa que una vez me dio un alumno en clase de teoría de números. Ya habíamos visto el lema de Euclides (
https://en.wikipedia.org/wiki/Euclid%27s_lemma), que dice que si $p$ es primo y $p|ab$, entonces $p|a$ ó $p|b$.
En vista de eso, como $3$ es primo y $3|n^2=n\cdot n$, entonces $3|n$, o $3|n$, así que no te escapas de que divida a $n$.
Por supuesto, la demostración de lema de Euclides pasa por los otros argumentos que se han mencionado.