Mostrando

Question

Un alumno mío ha estado estudiando por algunos teoría elemental del número. Ella vino por mi oficina hoy y preguntó si tenía alguna sugerencias sobre cómo probar la declaración

Si $m$ es impar entonces $\gcd(2^m-1,2^n+1)=1$.

Hace ya un tiempo tomó la teoría de números y no sé qué hacer. Dijo que está aprendiendo sobre congruencias, raíces primitivas y residuos de alimentación. Ella no ha tomado cualquier teoría del grupo.

Answer 1

Si un extraño prime $p$ divide $2^n+1$, luego el orden de $2$ modulo $p$ es incluso (es un divisor de a $2n$, pero no de $n$). Si un extraño prime $q$ divide $2^m-1$ $m$ impar, entonces el orden de $2$ modulo $q$ es impar (es un divisor de a $m$). Por lo tanto $p \neq q$. Desde $2^m - 1$ es extraño $m > 0$, en particular de todos los impares $m$, el máximo común divisor no puede ser uniforme. Así que no hay primer divide tanto, $2^n+1$$2^m-1$.

Alternativamente, se puede utilizar

$$\gcd (2^t-1, 2^u-1) = 2^{\gcd (t,u)}-1\tag{1}$$

para concluir

$$\gcd (2^m-1, 2^{2n}-1) = 2^{\gcd(m,2n)}-1.$$

Pero desde $m$ es impar, tenemos $\gcd (m,2n) = \gcd(m,n)$, y por lo tanto

$$2^{\gcd(m,2n)}-1 \mid 2^n-1,$$

que, desde

$$\gcd(2^n-1,2^n+1) = \gcd(2^n-1,2) \mid 2$$

y $2^{\gcd(m,2n)}-1$ es impar, implica $\gcd (2^{\gcd(m,2n)}-1,2^n+1) = 1$ y, por tanto,$\gcd(2^m-1,2^n+1) = 1$.

A ver $(1)$, escribir $u = q\cdot t + r$$0 \leqslant r < t$, y

$$2^u-1 = 2^r\left(2^{q\cdot t}-1\right) + \left(2^r-1\right),$$

que, desde la $2^t-1 \mid (2^t)^q-1$, los rendimientos de los

$$\gcd(2^t-1,2^u-1) = \gcd(2^t-1,2^r-1),$$

y continuando con el algoritmo de Euclides para los exponentes finalmente los rendimientos $(1)$.