Definición del dividendo en un problema gcd

Question

Utilice la inducción para demostrar que si $(a, b) = 1$ entonces $(a, b^n) = 1$ para todos $n \ge 1$ .

He montado el esqueleto de la prueba por inducción, pero tengo problemas para mostrar el paso más importante(?):

$(a, b^n) = 1$ para $n = 1$ por hipótesis.

Sea $1 = ax + by = \ldots =(ax + b^{n + 1}y)$ .

$(a, bb^n) | a, bb^n \to (a, bb^n) | (ax + b^{n + 1}y) \to (a, bb^n) | 1$ .

Tengo problemas para rellenar las igualdades que faltan $1 = ax + by = \ldots =(ax + b^{n + 1}y)$ . ¿Es eso posible?

Answer 1

El resultado se cumple claramente cuando $n=1$ . Demostramos que si el resultado se mantiene cuando $n=k$ entonces el resultado se cumple cuando $n=k+1$ .

Así que queremos demostrar que $(a,b^{k+1})=1$ . Supongamos por el contrario que $a$ y $b^{k+1}$ tienen un divisor común no trivial. Entonces $a$ y $b^{k+1}$ tienen un divisor primo común $p$ . Desde $p$ divide $b^k\cdot b$ se deduce que $p$ divide $b^k$ o $p$ divide $b$ . Pero $p$ no puede dividir $b$ ya que $(a,b)=1$ . Y $p$ no puede dividir $b^k$ ya que si lo hace tenemos $(a,b^k)\gt 1$ contradiciendo la hipótesis de inducción.

Observaciones: $1.$ Si se desea utilizar un argumento de identidad de Bezout, se podría decir que existen enteros $s$ y $t$ tal que $as+tb=1$ . Por la hipótesis de inducción, existen enteros $u$ y $v$ tal que $au+b^kv=1$ . Multiplicar. Nosotros obtenemos $$a(sau+sb^kv+tbu)+b^{k+1}(tbv)=1,$$ y el resultado es el siguiente.

$2.$ Otra forma de demostrar el paso de inducción es demostrar el lema preliminar de que si $(a,s)=1$ y $(a,t)=1$ entonces $(a,st)=1$ . Entonces para el paso de inducción tomamos $s=b^k$ y $t=b$ .

Answer 2

Si tenemos $x,y$ para que $$ ax+by=1 $$ entonces podemos utilizar el Teorema Binomial para obtener $$ \begin{align} 1 &=(ax+by)^n\\ &=\sum_{k=0}^n\binom{n}{k}(ax)^k(by)^{n-k}\\ &=\overbrace{\color{#C00000}{b^n}y^n}^{k=0\text{ term}}+\color{#C00000}{a}x\sum_{k=1}^n\binom{n}{k}(ax)^{k-1}(by)^{n-k} \end{align} $$

Answer 3

He aquí una prueba no inductiva:

Sea $b = p_1^{m_1}\cdots p_k^{m_k}$ sea la facotrización prima de $b$ . Entonces $b^n = p_1^{n\cdot m_1}\cdots p_k^{n \cdot m_k}$ .

Supongamos que $\gcd(a,b^n) = d > 1$ . Entonces $d = p_1^{l_1}\cdots p_k^{l_k}$ donde $0 \leq l_i \leq n \cdot m_i$ para $i = 0,1,\ldots,k$ y $l_i \geq 1$ para al menos un $i$ .

Sea $d' = p_1^{l_1 \mod{m_1}}\cdots p_k^{l_k \mod{m_k}}$ . Tenga en cuenta que $d>1 \Rightarrow d' >1$ . Claramente $d'|d$ y, por tanto $d'|a$ . Pero también $d'|b$ desde $0 \leq l_i \mod{m_i} \leq m_i$ para cada $i$ . Así $\gcd(a,b) \geq d' >1$ contradicción.