Demostrar que si $a^{k} \equiv b^{k} \pmod m $ y $a^{k+1} \equiv b^{k+1} \pmod m $ y $\gcd( a, m ) = 1$ entonces $a \equiv b \pmod m $

Question

Mi intento:

Desde $a^{k} \equiv b^{k}( \text{mod}\ \ m ) \implies m|( a^{k} - b^{k} )$ y $a^{k+1} \equiv b^{k+1}( \text{mod}\ \ m ) \implies m|( a^{k+1} - b^{k+1} ) $

Usando la identidad binomial, tenemos: $$a^{k} - b^{k} = ( a - b )( a^{k - 1} + a^{k - 2}b + a^{k - 3}b + ... ab^{k - 2} + b^{k - 1} )$$ $$a^{k + 1} - b^{k + 1} = ( a - b )( a^{k} + a^{k - 1}b + a^{k - 2}b + ... ab^{k - 1} + b^{k} )$$

Ahora hay dos casos:
1. Si $m|(a - b)$ hemos terminado.
2. Si no $m|( a^{k - 1} + a^{k - 2}b + a^{k - 3}b + ... ab^{k - 2} + b^{k - 1} )$ y $m|( a^{k} + a^{k - 1}b + a^{k - 2}b + ... ab^{k - 1} + b^{k} )$

Y a partir de aquí me quedé atascado, ya que no pude deducir nada de estas dos observaciones. Todavía tengo $(a, m) = 1$ y supongo que esta condición se utiliza para evitar $m$ divide por los dos lados de la derecha arriba.

Una pista sería muy apreciada.

Gracias,
Chan

Answer 1

Sugerencia $\rm \ b^k \equiv a^k \Rightarrow\ b^{k+1} \equiv\: b\ a^k \equiv\: a^{k+1} \Rightarrow\ b\equiv a\ $ al cancelar $\rm\ a^k.\: $ Recordemos que si $\rm\ (a,m) = 1\ $ entonces $\rm\:a\:$ es invertible, por lo que es cancelable, $\!\rm\bmod m,\,$ por ejemplo, por Bezout.

Generalmente $\rm\,\color{#c00}{A\equiv B},\, aA\equiv b\color{#c00}B\,\Rightarrow\, aA\equiv b\color{#c00}A\,\Rightarrow\, a\equiv b\,$ si $\rm\,A\,$ es cancelable. OP es $\rm\,A,B = a^k,b^k$

La misma prueba funciona en cualquier anillo donde $\rm\:a\:$ es una unidad, es decir, invertible. La prueba anula las unidades $\rm\ a^k = b^k\ $ de ambos lados de $\rm\ a^{k+1} = b^{k+1}\ $ para obtener $\rm\ a = b\:.\:$ Aquí utilizamos esa unidad $\rm\:a\ \Rightarrow\: $ unidad $\rm\: b\ $ por $\rm\:b\mid b^k\mid a^k,\,$ y las unidades se cierran bajo productos/divisores: $\rm\ xy\:$ unidad $\rm\iff\ x\:$ unidad y $\rm\:y\:$ unidad.

Está más claro deshomogeneizado utilizando $\rm\ c = b/a\:,\: $ a saber $\rm\ 1 = c^k\ \Rightarrow\ c = c^{k+1} = 1\:$ .

Answer 2

Esta es la idea: Demostrar que (2) es imposible. Supongamos que $$m|\left( a^{k-1}+a^{k-2}\cdot b+\cdots + b^{k-1}\right)$$ y $$m|\left(a^{k}+a^{k-1}\cdot b+\cdots + b^{k}\right)$$ A continuación, reste $b$ veces el primer entero desde el segundo entero. Es decir, considere $$\left( a^{k}+a^{k-1}\cdot b+\cdots + b^{k} \right) -b\cdot \left( a^{k-1}+a^{k-2}\cdot b+\cdots + b^{k-1} \right)= a^k$$

De ello se desprende que $m$ divide $a^k$ pero eso es imposible. (¿Por qué?)

Espero que eso ayude.

Answer 3

Tenemos $$m|(a^{k}+a^{k-1}b+a^{k-2}b^2 + \cdots + ab^{k-1}+b^k)$$ $$-t(a^{k-1}+a^{k-2}b+a^{k-3}b^2+ \cdots + ab^{k-2} + b^{k-1}) = a^k$$

que es imposible.

Answer 4

Esto está relacionado con lo que dijo Bill Dubuque, pero es más elemental:

Desde $a^k = b^k$ mod $m$ , uno tiene $m | (a^k - b^k)$ , y de forma similar $m | (a^{k+1} - b^{k+1})$ . Así, por la primera ecuación $m$ divide $b(a^k - b^k) = (a^kb - b^{k+1})$ . Restando, tenemos que $m | (a^{k+1} - b^{k+1}) - (a^kb - b^{k+1}) = a^{k+1} - a^kb = a^k(a - b)$ . Pero como $(a,m) = 1$ El hecho de que $m | a^k(a - b)$ significa $m | a - b$ o, por el contrario $a = b$ mod $m$ que es lo que necesitabas mostrar.

Answer 5

• $a\equiv b\pmod{n} \quad\textrm{and}\quad b\equiv c\pmod{n}\Rightarrow a\equiv c\pmod{n}$

• $a\equiv b\pmod{n}\Leftrightarrow b\equiv a\pmod{n}$

• $a\equiv b\pmod{n}\Rightarrow ac\equiv bc\pmod{n}$ para cualquier $c$

La lista puede ser suficiente para conseguir $$a^kb\equiv a^ka\pmod{m}.$$

Me gustaría mencionar un teorema que acabo de aprender de Hardy Introducción a la teoría de los números :

TEOREMA 54. Si $(k, m) = d$ entonces $$kx\equiv ky\pmod{m}\Rightarrow x\equiv y\pmod{\frac{m}{d}},$$ y a la inversa.

Este teorema te dice que cuándo y cómo puedes "cancelar" algo en la ecuación de congruencia. Ahora basta con demostrar que $(a^k,m)=1$ , lo que puede hacerse mediante reductio ad absurdum (prueba por contradicción).

---

Cuando uno resuelve algún problema de congruencia, es mejor que tenga a mano o al menos en mente una lista de las propiedades de la congruencia. Esto es conveniente para su pensamiento. Como dijo Terence Tao en su " Resolución de problemas matemáticos ", poner todo por escrito ayuda de tres maneras:

1. para tener una referencia fácil más tarde de referencia;
2. el papel es algo bueno para mirar fijamente cuando estás atascado;
3. el acto físico de escribir de lo que sabes puede desencadenar nuevas inspiraciones y conexiones.