división con resto

Question

Tengo problemas con la prueba de estos ejercicios de mi estudio de matemáticas. En el caso de (a), he intentado utilizar la división larga para encontrar el resto de (2^a) - 1 y (2^b) - 1, pero no ha funcionado. ¿Puedes ayudarme a demostrarlo?

Sean a, b en Z(>0)

(a) Sea r el resto de a por división con b. Demuestre que (2^r) - 1 es el resto de (2^a) - 1 por división con (2^b) - 1

(b) Demuestre: (2^b) - 1 | (2^a) - 1 si y sólo si b|a.

Answer 1

Supongamos que $a=bq+r$ y $2^{a}-1=q'\left(2^{b}-1\right)+2^{r}-1$ .

de la segunda ecuación obtenemos

$$q'=\frac{2^{a}-2^{r}}{2^{b}-1}=\frac{2^{bq+r}-2^{r}}{2^{b}-1}=2^{r}\frac{2^{bq}-1}{2^{b}-1}=2^{r}\sum_{k=0}^{q-1}2^{b}\in\mathbb{Z}$$ cuando la última igualdad es de la fórmula de las serias geométricas.

para la prueba de (b), utilice (a) por supuesto

Answer 2

A continuación se presentan las pruebas:

1. De lo dado obtenemos $a=kb+r$ para algún número entero $k$ , $$2^a-1=2^{(kb+r)}-1$$ que es $$2^{(kb)}.2^r-1$$ $$((2^b-1)+1)^{k}.2^r-1$$ Ahora todos los términos de la expansión binomial de $((2^b-1)+1)^{k}$ será múltiplo de $2^b-1$ excepto en el caso de $1$ . Salvo este término todos dan módulo cero por lo que obtenemos $1.2^r-1$ izquierda que es el resto. Para la expansión binomial de $(a+b)^n$ véase Expansión binomial .
2. Si $r=0$ es decir. $b$ divide $a$ entonces el resto de $2^a-1$ dividido por $2^b-1$ se convierte en $2^r-1=0$ Así que $2^b-1$ divide $2^a-1$ Si lo contrario es cierto, entonces $2^r-1=0$ que sólo puede ocurrir para $r=0$ Así que $b$ divide $a$ Hemos probado las dos formas, por lo que hemos demostrado la condición "si" y "sólo".

Answer 3

Sugerencia :

Si $a=db+r$ donde $0\leq r<b$ entonces:

$2^{a}-1=2^{r}\left(2^{b}-1\right)\left(2^{bd-b}+2^{bd-2b}+\cdots+1\right)+2^{r}-1$