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.
Queremos saber si para cierto $n$ existe un $2 \leq a \leq n - 2$ tal que $$\gcd(a, n - a) = 1 \iff \gcd(a, n) = 1$$Si hay alguno ya sabemos que $n$ debe ser simple ya que tomando $b = n - a$ tenemos un $a > 1$ y $b > 1$ con $\gcd(a, b) = 1$ tal que $a + b = n$.
Como siempre $\gcd(1, n) = 1$ y $\gcd(n - 1, n) = 1$, esto es equivalente a encontrar los $n$ tal que $\phi(n) \geq 3$, donde $\phi(n)$ cuenta los coprimos con $n$ entre $1$ y $n - 1$.
Como
$$n = \prod p_i^{k_i} \Rightarrow \phi(n) = \prod (p_i - 1)p_i^{k_i - 1}$$
Luego si $n$ tiene en su factorización en primos un primo mayor o igual a $5$, $\phi(n) \geq 5 - 1 = 4 > 3$ por lo que todos ellos son números simples. Solo tenemos que ver entonces números que sólo tienen a $2$ y $3$ como factores primos. Además, si como $(2 - 1)2^{3-1} = 4 > 3$, y $(3 - 1)3^{2-1} = 6 > 3$, si $n = 2^{k_1}3^{k_2}$, $0 \leq k_1 \leq 2$ y $0 \leq k_2 \leq 1$. Luego solo basta calcular $\phi(n)$ para estos $6$ números.
$$\phi(1) = 1 \\ \phi(2) = 1 \\ \phi(3)=2 \\ \phi(4)=2 \\ \phi(6)=2 \\ \phi(12)=4$$
Con lo cual el conjunto de los números simples es $\mathbb{N} \setminus \{1, 2, 3, 4, 6\}$. $\blacksquare$
