Un entero positivo se dice simple si se puede escribir como suma de dos enteros positivos mayores que $1$ y coprimos entre sí. Por ejemplo, $102=35+72$ es simple pues $35$ y $72$ son coprimos ya que el único divisor común es el $1$.
Determinar todos los enteros positivos simples. Aclaración: Dos enteros positivos $a,b$ son coprimos si el máximo común divisor entre $a$ y $b$ es $1$.
"La matemática es para pensar. El fútbol es para sacar mi instinto animal y decirle al árbitro hdp te voy a m4t4r." Anónimo
El problema nos dice que:
$n = a+b$
Con $mcd(a, b) = 1$, $n > 1$ y $a, b \in \mathbb Z^+$. Para evitar problemas con los casos bases podemos considerar $n, a, b$ arbitrariamente grandes.
Luego, tomemos $p$ tal que:
$$\frac{n}{2} < p < n$$
$$n = n - p + p$$
La primera afirmación es cierta por el teorema de Bertrand y la segunda simplemente sumamos y restamos $p$. Ahora veamos que por algoritmo de Euclides: $mcd(n-p, p) = mcd(n, p) \Rightarrow mcd(n, p) = 1 \vee mcd(n, p) = p$. Si miramos este ultimo caso, tenemos que para un entero $m$ se cumple que $p | n \Rightarrow n = p.m \Rightarrow \frac{p.m}{2} < p \Rightarrow m < 2 \Rightarrow m = 1 \Rightarrow p = n$ lo cual es una contradicción ya que $p < n$, luego $mcd(n-p, p) = 1$.
Esta claro que $p \neq 1$ pero eventualmente $n-p = 1 \Rightarrow n = p+1$. Para este caso tomemos un primo $q$ tal que:
$$\frac{p}{2} < q < p$$
$$n = p+1 = p+1-q + q$$
Se sigue que $mcd(p+1-q, q) = mcd(p+1, q) \Rightarrow mcd(p+1, q) = 1 \vee mcd(p+1, q) = q$. Si ocurre el primer caso, el problema esta termimado ya que $p+1-q>1$ y $q>1$. Analizando el ultimo caso tenemos que para un entero $m$ se cumple: $q | p+1 \Rightarrow p+1 = q.m \Rightarrow \frac{q.m-1}{2} < q \Rightarrow q.m < 2q +1$ de lo cual se desprende que $m = 1 \vee m = 2$. En caso que $m = 1$ entonces $q = p+1$ y como cambian de paridad y ambos son primos, entonces la única solución es $q = 3 \land p = 2$ pero $q < p$, clara contradicción. Se sigue que $m = 2 \Rightarrow p + 1 = 2q$
Hasta el momento tenemos $n = p+1 = 2q$. Ahora veamos que $2q = 2q - 3 + 3$ y $mcd(2q- 3, 3) = mcd(q, 3) = 1 \land q \neq 3$. Finalmente, nos queda checkear que $2q-3 > 1 \Rightarrow q > 4$. Entonces acabamos de construir un ejemplo para todo $n > 4 \land n \neq 6$. Es fácil ver que no existe otra forma de expresar a estos números excluidos como suma de dos coprimos, lo cual termina el problema.
El problema nos dice que:
$n = a+b$
Con $mcd(a, b) = 1$, $n > 1$ y $a, b \in \mathbb Z^+$. Para evitar problemas con los casos bases podemos considerar $n, a, b$ arbitrariamente grandes.
Luego, tomemos $p$ tal que:
$$\frac{n}{2} < p < n$$
$$n = n - p + p$$
La primera afirmación es cierta por el teorema de Bertrand y la segunda simplemente sumamos y restamos $p$. Ahora veamos que por algoritmo de Euclides: $mcd(n-p, p) = mcd(n, p) \Rightarrow mcd(n, p) = 1 \vee mcd(n, p) = p$. Si miramos este ultimo caso, tenemos que para un entero $m$ se cumple que $p | n \Rightarrow n = p.m \Rightarrow \frac{p.m}{2} < p \Rightarrow m < 2 \Rightarrow m = 1 \Rightarrow p = n$ lo cual es una contradicción ya que $p < n$, luego $mcd(n-p, p) = 1$.
Esta claro que $p \neq 1$ pero eventualmente $n-p = 1 \Rightarrow n = p+1$. Para este caso tomemos un primo $q$ tal que:
$$\frac{p}{2} < q < p$$
$$n = p+1 = p+1-q + q$$
Se sigue que $mcd(p+1-q, q) = mcd(p+1, q) \Rightarrow mcd(p+1, q) = 1 \vee mcd(p+1, q) = q$. Si ocurre el primer caso, el problema esta termimado ya que $p+1-q>1$ y $q>1$. Analizando el ultimo caso tenemos que para un entero $m$ se cumple: $q | p+1 \Rightarrow p+1 = q.m \Rightarrow \frac{q.m-1}{2} < q \Rightarrow q.m < 2q +1$ de lo cual se desprende que $m = 1 \vee m = 2$. En caso que $m = 1$ entonces $q = p+1$ y como cambian de paridad y ambos son primos, entonces la única solución es $q = 3 \land p = 2$ pero $q < p$, clara contradicción. Se sigue que $m = 2 \Rightarrow p + 1 = 2q$
Hasta el momento tenemos $n = p+1 = 2q$. Ahora veamos que $2q = 2q - 3 + 3$ y $mcd(2q- 3, 3) = mcd(q, 3) = 1 \land q \neq 3$. Finalmente, nos queda checkear que $2q-3 > 1 \Rightarrow q > 4$. Entonces acabamos de construir un ejemplo para todo $n > 4 \land n \neq 6$. Es fácil ver que no existe otra forma de expresar a estos números excluidos como suma de dos coprimos, lo cual termina el problema.
Si $n$ es impar: $n = (2) + (n - 2)$ con $a = 2$, $b = n-2$ Formando así todos los impares mayores o iguales a $5$
Si $n$ es par:
Caso 1: $\frac{n}{2}$ es par $n = (\frac{n}{2}+1) + (\frac{n}{2} - 1)$ Entonces si $a = \frac{n}{2}+1$ y $b = \frac{n}{2}-1$ estamos ya que estos dos son claramente coprimos. Dado que $a,b >1 \Rightarrow \frac{n}{2}-1 > 1 \iff n > 4$.
Caso 2: $\frac{n}{2}$ es impar: $n = (\frac{n}{2}+2) + (\frac{n}{2} -2)$ Con $a = \frac{n}{2}+2$ y $b = \frac{n}{2}-2$ y $\frac{n}{2} - 2 > 1 \iff n > 6$
Es fácil ver que para $1, 2, 3, 4, 6$ no hay solución.
Muchas gracias a ambos! Y, claramente, eternamente agradecido con el foro, definitivamente no hubiera sido posible sin tener la posibilidad de aprender de los mejores.
Todavía queda camino por delante, por lo que voy a ir por mas... les dejo este mensaje a los que recién empiezan:
Empecé en $2022$ en OMA. El primer año no le di tanta importancia, el segundo le metí un poco mas y este año deje todo de lado para poder ganar algo. En el nacional vi que la mayoría de personas que sacaban podio, habían empezado todos en ñandu, y algunos me decían que era imposible ganar si no hacia OMA desde $5$to grado de primaria. Hoy puedo decir que la hipótesis era falsa y que todo se puede si se esfuerzan lo suficiente.
