Probar que si $a$ $b$ son impares, coprime números, a continuación, $\gcd(2^a +1, 2^b +1) = 3$

Question

Probar que si $a$ $b$ son impares, coprime números, a continuación,$\gcd(2^a +1, 2^b +1) = 3$.

Estaba pensando entre las líneas de:

Desde $a$ $b$ son coprime números, $\gcd(a,b)=1$. Entonces existen enteros $x$ $y$ de manera tal que, $ax+by=1$.

Entonces, $a=(1-by)/x$, $b=(1-ax)/y$

Así que si escribo $2^a+1$ como:

$2^{(1-by)/x}+1$

Entonces puedo decir que la expresión anterior es equivalente a 0 (mod 3)?

Answer 1

Tenga en cuenta que tanto $2^a+1$ $2^b+1$ son impares, por lo que cualquier divisor común es impar.

Ahora, si $d$ divide $2^a+1$$2^b+1$, entonces también se divide $(2^a+1)-(2^b+1) = 2^a-2^b$, por lo tanto se divide $2^{\min(a,b)}(2^{|a-b|}- 1)$. Pero desde $d$ es impar, entonces $d$ divide $2^{|a-b|}-1$. Es decir, si, por ejemplo, $a\geq b$, luego $$d|2^{a}-1,2^b-1 \Longleftrightarrow d|2^a-1, 2^b-1, 2^{a-b}-1.$$ Pero si $d$ divide tanto a a$2^{a-b}-1$$2^b-1$, a continuación, divide $$2^b(2^{a-b}-1) + (2^b-1) = 2^a-1.$$ Así: $$d|2^a-1,2^b-1 \Longleftrightarrow d|2^b-1, 2^{a-b}-1.$$ Estamos asumiendo $a\geq b$; tenga cuidado con esa suposición; de forma más general, tenemos: $$\text{For }a,b\text{ odd, }\gcd(2^a-1,2^b-1) = \gcd(2^{\min(a,b)}-1, 2^{|a-b|}-1).$$

Esto se parece mucho a la dpc de identidad $$\gcd(x,y) = \gcd(y,x-y),$$ lo cual es muy útil. Tal vez usted puede hacer el trabajo para usted?

Answer 2

Muy útil, de hecho: Si $a$ $b$ son relativamente primos, existen enteros $x$ $y$ tal que $ax+by=1$.

Podemos organizar para$x$$\ge 0$$y$$\le 0$. Así que no son enteros no negativos $u$ $v$ tal que $au=bv+1$. Así $$2^{au}=2^{bv+1}=2\cdot 2^{bv}. \qquad\text{(Equation 1)}$$

Deje $m$ ser cualquier divisor común de a$2^a+1$$2^b+1$. A continuación,$2^a \equiv -1\pmod{m}$$2^b\equiv -1 \pmod m$. De ello se sigue que $$2^{au} =(2^a)^u \equiv (-1)^u \pmod{m} \qquad\text{and}\qquad 2^{bv} =(2^b)^v \equiv (-1)^v \pmod{m}.$$ A partir de la Ecuación de $1$, llegamos a la conclusión de que $$(-1)^u \equiv 2\cdot (-1)^v\pmod{m}.$$ Desde $a$ $b$ son impares, $u$ $v$ han opuesto a la paridad. Por lo tanto $-1\equiv 2\pmod {m}$, $3\equiv 0 \pmod m$, y por lo tanto $m$ divide $3$.

Si $c$ es impar, entonces $2^c\equiv -1\pmod{3}$, lo $3$ divide $2^c+1$. Por lo tanto $3$ divide nuestro mcd. Pero nuestro mcd divide $3$, por lo que es $3$.

Answer 3

Si $d\mid 2^a+1$,$2^a \equiv -1 \pmod d$. Pero entonces eso significa que el orden de $2\pmod d$ debe ser un divisor de a $2a$. Del mismo modo, si $d\mid 2^b +1$, la orden de $2 \pmod d$ debe dividir $2b$. Pero eso significa que el fin de la $2\pmod d$ debe dividir $(2a,2b)=2$. De modo que el orden de $2\pmod d$ debe ser un divisor de a $2$ o $2^2=1\pmod d$. Por lo $d=3$ o $d=1$.

Answer 4

Una de las formas posibles de extraño coprime números es:

$a=2m-n$ $b=m$ , (ver en esta página)

Así que podemos escribir las siguientes igualdades:

$2^{a}+1=2^{2m-n}-2+3=2(2^{2m-n-1}-1)+3$

$2^{b}+1=2^{m}-2+3=2(2^{m-1}-1)+3$

Así que con el fin de demostrar que el $\gcd(2^{a}+1,2^{b}+1)=3$ tenemos que demostrar que:

$\gcd(2^{2m-n-1}-1,2^{m-1}-1)=2^{\gcd(2m-n-1,m-1)}-1=3\cdot p $ para algún número natural $p$

La última igualdad es verdadera sólo si: $\gcd(2m-n-1,m-1)=2\cdot k$ (número par) para todos los $m,n$. Desde $m$ $n$ son números impares se puede mostrar fácilmente que esto siempre es cierto.

Del mismo modo, usted puede mostrar a los otros dos formas de $a$ $b$ que $\gcd(2^{a}+1,2^{b}+1)=3$