Si $\gcd(a,b)=1$, ¿cómo puedo encontrar los valores que $\gcd(a+b,a^2+b^2)$, posiblemente, puede tomar? No puedo encontrar una manera de utilizar cualquiera de los elementales de la divisibilidad y mcd teoremas para encontrarlos.
Respuestas
¿Demasiados anuncios?
Tenemos $a^2 + b^2 - a(a+b) = b^2 - ab = -b (a-b)$$a^2 + b^2 - b(a+b) = a^2 - ba = a (a-b)$.
Así que si $d$ divide tanto a a$a+b$$a^2+b^2$, $d$ divide $$\gcd(a (a-b), b (a-b)) = \gcd(a, b) (a-b) = a - b.$$
Por lo $d$ divide $a+b + a - b = 2a$$a+b - (a - b) = 2b$.
Por lo $d$ divide $2\gcd(a,b)=2$.
Así que las posibilidades de la $\gcd$ parecen ser$1$$2$, y claramente se producen.
Hurkyl
Puntos
57397
$$\begin{align} \gcd(a+b, a^2 + b^2) &= \gcd(a+b, a^2 + b^2 - a(a+b)) \\&= \gcd(a+b, b^2 - ab) \\&= \gcd(a+b, b^2 - ab + b(a+b)) \\&= \gcd(a+b, 2b^2) \end{align} $$
Ahora, $\gcd(a+b,b) = \gcd(a,b) = 1$, por lo que podemos deshacernos de los factores de $b$
$$ \gcd(a+b, a^2 + b^2) = \gcd(a+b, 2) $$
La estrategia que se utiliza todavía la idea básica del algoritmo de Euclides; ya que no podía comparar valores numéricos, que en vez simplificado trabajando para eliminar la variable $a$, empezando con el más grande poder de $a$.
Anthony Shaw
Puntos
858
Desde $\gcd(a,b)=1$, la Identidad de Bezout dice que tiene un $x$$y$, de modo que $$ ax+by=1\etiqueta{1} $$ Tenga en cuenta que $$ \begin{align} 2a^2&=(a^2+b^2)+(a+b)(a-b)\\ 2ab&=(a+b)^2-(a^2+b^2)\\ 2b^2&=(a^2+b^2)-(a+b)(a-b)\\ \end{align}\etiqueta{2} $$ Por lo tanto, la incorporación de $(1)$$(2)$, $$ \begin{align} 2 &=2(ax+by)^2\\ &=2a^2x^2+4abxy+2b^2y^2\\ &=\Big((a^2+b^2)+(a+b)(a-b)\Big)x^2\\ &+2\Big((a+b)^2-(a^2+b^2)\Big)xy\\ &+\Big((a^2+b^2)-(a+b)(a-b)\Big)y^2\\ &=\color{#00A000}{(x-y)^2}\color{#C00000}{(a^2+b^2)} +\color{#00A000}{((x^2-y^2)(a-b)+2xy(a+b))}\color{#C00000}{(a+b)}\tag{3} \end{align} $$ La ecuación de $(3)$ dice que $$ \gcd(a+b,a^2+b^2)\,|\,2\la etiqueta{4} $$ Tenga en cuenta que$\gcd(1+2,1^2+2^2)=1$$\gcd(1+3,1^2+3^2)=2$, por lo tanto $1$ $2$ son posibles.
Math Gems
Puntos
14842
Por abajo: $\rm\ \ \ (a\!+\!b,\ a^2\!+\!b^2)\, =\, (2,a\!+\!b)\ $ al $\rm (a,b)=1,\ $ de los rendimientos del tratado de dpc.
Teorema $\rm\ \ (a\!+\!b,\ a^2\!+\!b^2)\, =\, (2a^2,\ \ 2ab,\ \ 2b^2,\ a\!+\!b)\, =\, (2(a,b)^2\!,\ a\!+\!b)$
Prueba de $\rm\,\ mod\ a\!+\!b\!:\ a^2\!+\!b^2 \equiv 2a^2\! \equiv -2ab \equiv 2b^2\ \, $ $\rm\,a\!+\!b\,$ divide $\rm\color{#0A0}{green}$ términos que a continuación se
$$\rm a^2\!+\!b^2 = (\color{#0A0}{b^2\!-\!a^2})+2a^2 = (\color{#0A0}{a\!+\!b})^2\!-2ab = (\color{#0A0}{a^2\!-\!b^2})+2b^2 $$
Comentario $\ $ se utilizó $\rm\: (c,d_i) = (c,d)\ $ si $\rm\ d_i\equiv d\ (mod\ c);\:$ $\rm\: (c,d) = (c,\ d\ mod\ c),\:$ el paso recursivo (descenso) en el corazón del algoritmo de Euclides (básicamente, lo que hemos utilizado).
El final igualdad de $\rm\ 2(a,b)^2 =\, 2(a^2,ab,b^2)\:$ es por mcd leyes (asociativa,distributiva, etc), es decir,
$$\rm\ (a,b)(a,b) = ((a,b)a,(a,b)b) = (a^2,ba,ab,b^2) = (a^2,ab,b^2)$$
Pedro Tamaroff
Puntos
73748
Tenga en cuenta que $a^2+b^2=(a+b)^2-2ab$. Por lo tanto $a^2+b^2\equiv -2ab\mod a+b$ y usted necesita encontrar a $(a+b,-2ab)=(a+b,2ab)$. Puede usted pasar?
AGREGAR Nota que $a,b$ no pueden ser ambos inclusive. Si uno es impar y el otro es, incluso, a continuación,$2\not\mid a+b$, lo $(a+b,2ab)=(a+b,ab)$. Pero si $p>2$ es una de las principales con el $p\mid a+b,ab$ $p\mid a$ o $p\mid b$, ya que el $p\mid ab$. Pero, en cualquier caso, desde la $p\mid a+b$, esto daría $p \mid b$ (si $p\mid a$) o $p \mid a$ (si $p\mid b)$, contrario a $(a,b)=1$. Por lo tanto $(a+b,ab)=1$.
Si $a,b$ son ambos impares, a continuación, $a+b$ es incluso y $2\mid (a+b,2ab)$. Y de nuevo, si $p$ es una extraña primer factor de $p\mid 2ab\implies p\mid ab$ y el mismo argumento anterior pasa a través de. Por lo tanto, siempre $(a,b)=1$, $$(a+b,a^2+b^2)=\begin{cases} 1 &\text{if one of } a,b \text{ is odd}\\2&\text{if both} a,b\text{ are odd}\end{cases}$$
