¿Se puede solucionar este rompecabezas sin fuerza bruta?

Question

Considere la posibilidad de enteros positivos $a$ $b$ donde $a \ge b$ y la suma de $\frac{a+1}{b}+\frac{b+1}{a}$ es también un número entero. Hallar la suma de todos los $a$ valores de menos de $1000$ que cumplen estos criterios.

Por ejemplo, si $a=3$$b=2$, luego $$\frac{a+1}{b}+\frac{b+1}{a} = \frac{3+1}{2}+\frac{2+1}{3} = 3$$ que es un entero y proporciona un valor jurídico de $a$. El problema pregunta para todos los valores de $a \lt 1000$. Estoy asumiendo que un determinado $a$ es suficiente si no existe aún una $b \le a$ que satisface la condición.

Este problema puede ser resuelto simplemente escribir un programa de ordenador que de doble bucle a través de los números enteros positivos a menos de 1000, las pruebas de cada caso, sin embargo, me pregunto si hay una forma más general y abstracta manera de resolverlo.

Aquí están algunas ideas ... no estoy seguro de lo útiles que son:

1. $\frac{a+1}{b}+\frac{b+1}{a}$, que es un entero puede escribirse como $\frac{a}{b}+\frac{b}{a}+\frac{1}{b}+\frac{1}{a}$.
2. el cocientes $(a+1) \div b$ $(b+1) \div a$ son también números enteros o sus partes fraccionarias agregar a a $1$.

Answer 1

Utilizamos una técnica estándar llamado Vieta de salto, que tiene un fascinante y sorprendente de la historia reciente.

Supongamos $a^2 + a + b^2 + b = kab$ para algunos entero $k$. Entonces, a escribir esto como un polinomio en $a$ con coeficientes enteros:

$$a^2 - (kb-1) a + (b^2+b) = 0,$$

podemos ver que si $(a,b)$ es una de las raíces de la cuadrática de arriba, a continuación, la otra es $c = (b^2+b)/a$, lo cual es claramente positiva. Además, dado que las dos raíces de la suma de un número entero, es decir,$kb-1$, $c$ es necesariamente un entero positivo.

Ahora vamos a considerar los tamaños. Si $a>b$,$a \ge b+1$$c = b(b+1)/a \le b$. Así que si $(a,b)$ es una solución para el problema, entonces cualquiera de las $a=b$ o $(b,c)$ es una solución más pequeña, con el mismo valor de $k$. Ya que todos los valores siguen siendo positivas, que sólo se puede obtener más pequeñas de un número finito de veces, por lo que finalmente debemos llegar a una solución donde la $a=b$.

En el caso de que $a=b$ es muy fácil: debemos tener $k = 2 + 2/a$, por lo que las únicas soluciones de este tipo se $(1,1)$$k=4$$(2,2)$$k=3$.

Por último, ya que cada solución que finalmente se reduce a $(1,1)$ o $(2,2)$ por el proceso de reducción, se puede recuperar todas las soluciones mediante la ejecución del proceso en sentido inverso, a partir de $(1,1)$$(2,2)$:

$$(1,1) \leftarrow (2,1) \leftarrow (6,2) \leftarrow (21,6) \leftarrow \cdots $$ $$(2,2) \leftarrow (3,2) \leftarrow (6,3) \leftarrow (14,6) \leftarrow \cdots $$

Los valores que crecen de forma exponencial, por lo que no toma mucho tiempo para cualquier secuencia exceder $1000$.

Answer 2

En primer lugar, quiero mencionar que no estoy muy familiarizado con el operador mod así que si yo lo uso de forma incorrecta por favor me informan.

Porque $$\frac{a+1}{b}+\frac{b+1}{a}=\frac{a^2+a+b^2+b}{ab}$$ es obvio que si $\frac{a+1}{b}+\frac{b+1}{a}$ es un número entero, entonces $a^2+a+b^2+b$ uniformemente divide en $ab$. Por lo tanto

$$a^2+a+b^2+b=0 \mod{ab}$$ $$a^2+2ab+b^2+a+b=0 \mod{ab}$$ $$(a+b)^2+(a+b)=0 \mod{ab}$$ $$(a+b)(a+b+1)=0 \mod{ab}$$

Así que o $a+b=0 \mod{ab}$ o $a+b+1=0 \mod{ab}$

Ahora vamos a colocar el operador mod y deje $a+b=k_1ab$ $a+b+1=k_2ab$ donde $k_1$ $k_2$ son números naturales. La solución para $a$ da $a=\frac{b}{k_1b-1}$ $a=\frac{b+1}{k_2b-1}$

¿Responde esto a tu pregunta o al menos dar una idea?