[La pregunta en el cuerpo de la OP es un poco diferente de la pregunta en el título, y me parece más interesante. Así que esa es la pregunta a la que respondo].
Es común centrarse en el hecho de que es fácil enunciar problemas de teoría de números, ya que los conceptos básicos de la teoría de números son bastante elementales. Esto es cierto, pero creo que merece la pena señalar otro aspecto de la teoría de números que puede hacer que sus problemas sean difíciles, y es que la naturaleza elemental del enunciado de ciertos problemas puede desmentir las estructuras ocultas que subyacen a su naturaleza más profunda y (eventualmente) a su solución.
Por ejemplo, considere el problema de escribir números primos de la forma $x^2 + n y^2$ . En $n = 1$ hay una obstrucción de congruencia obvia mod $4$ para resolver $p = x^2 + y^2$ lo que implica que si $p$ es impar, entonces de hecho $p \equiv 1 \bmod 4$ . Fermat demostró que esta condición necesaria es también suficiente.
Del mismo modo, si queremos escribir $p = x^2 + 5y^2$ entonces si $p \neq 2, 5$ hay son obstrucciones obvias: $p$ debe ser un mod cuadrado $5$ y debe ser una suma de cuadrados mod. $4$ y, por tanto $1 \bmod 4$ . Todo ello implica que $p \equiv 1$ o $9 \bmod 20$ . De nuevo, Fermat (creo) demostró que esta condición necesaria es suficiente.
Ahora considere escribir $p = x^2 + 23y^2$ . No hay obstrucción mod $4$ , por lo que el único obstáculo evidente es que $p$ debe ser un mod cuadrado $23$ . Sin embargo, esta condición necesaria ya no es suficiente. Por ejemplo $p = 13$ es un cuadrado mod $23$ pero no se puede escribir de la forma $x^2 + 23y^2$ y lo mismo ocurre con $p = 29$ . (De hecho $p = 59$ es el primer primo que puede escribirse así).
La comprensión de este fenómeno condujo a muchos descubrimientos profundos de la estructura en la teoría de números, como la reciprocidad cuadrática y la teoría de las formas cuadráticas de Gauss. Éstas, a su vez, contribuyeron en gran medida al desarrollo de la teoría algebraica de números y la teoría de campos de clases. Desde un punto de vista moderno, la diferencia entre el caso $n = 23$ y los otros que consideré es que el grupo de clase de $\mathbb Z[(1+\sqrt{-23})/2]$ no es un producto de grupos cíclicos de orden $2$ --- es de hecho un grupo de orden $3$ .
Otro ejemplo son las fórmulas de sumas de cuadrados.
Existe una fórmula para el número de formas de escribir un número como suma de dos cuadrados: $$r_2(n) = 4\sum_{d |n} \chi(d),$$ donde $\chi(d) = \pm 1$ si $d \equiv \pm 1 \bmod 4,$ y $0$ si $d$ es par.
También existe una fórmula para el número de formas de escribir un número como suma de cuatro cuadrados: $$r_2(n) = 8 \sum_{d | n, 4\not\mid n} d.$$
Existen fórmulas similares para sumas de seis u ocho cuadrados, pero no para sumas superiores a número de cuadrados. Es difícil entender esto sin darse cuenta de que estas fórmulas se rigen por la estructura de ciertos espacios de formas modulares, que no contienen cuspformas en pesos bajos, pero que eventualmente contienen cuspformas, para las que no se dispone de fórmulas elementales.
Hay una enorme cantidad de estructura presente en la teoría de números, a pesar de la forma elemental en la que se pueden plantear algunos de sus problemas. Creo que ésta es una de las razones por las que sus problemas pueden ser tan difíciles de resolver; porque su enunciado a menudo no hace evidente esta estructura, pero encontrarla es necesario para resolver los problemas. (La hipótesis de Riemann puede considerarse una ilustración actual de esta dificultad).