divide a $ab$ $3^a+1$ y $3^b+1$

Question

Encuentra todos los enteros positivos $a,b$ tal divide a que $ab$ $3^a+1$ y $3^b+1$.

Está claro que $3$ no puede dividirse o $a$ o $b$, porque no divide a $3$ $3^a+1$ o $3^b+1$.

$(a,b)=(1,1),(2,1),(1,2)$ todo el trabajo. Si $b=1$, la condición se reduce a $a$ divide $3^a+1$ $4$, que $a=1,2,4$, pero esto ya ha sido cubierto.

[Fuente: problema de competencia coreana]

Answer 1

Vamos a empezar con un lema.

Lema Para un entero $m>2$, $gcd(m^{a}-1,m^{b}-1)=m^{gcd(a,b)}-1$

Prueba Supongamos wlg que $a>b$. Entonces \begin{align*} gcd(m^{a}-1,m^{b}-1)= \enspace&gcd(m^{a}-1,m^{a-b}(m^{b}-1))\\ =\enspace&gcd(m^{a}-1,m^{a-b}-1)\\ =\enspace&gcd(m^{b}-1,m^{a-b}-1) \end{align*} desde $gcd(x,y)=gcd(x,x-y)$. Reiterando, $gcd(m^{a}-1,m^{b}-1)=gcd(m^{b}-1,m^{r}-1)$ $r$ siendo el resto de la euclidiean división de $a$$b$. Podemos proceder así con Euclides' algortihm hasta que llegamos $gcd(m^{a}-1,m^{b}-1)=gcd(m^{dk}-1,m^{d}-1)=m^{d}-1$ donde $d=gcd(a,b)$.

Desde $3^{a}+1$ divide $9^{a}-1$, aquí conseguimos $ab | 9^{d}-1$$d=gcd(a,b)$. Vamos a demostrar que esto implica $d=1$, por lo tanto la solución del problema, desde entonces,$ab | 8$. Supongamos $d>1$ y deje $p$ ser el menor factor primo de $d$. A continuación,$9^{d}=1 \pmod p$. El orden de $9$ debe dividir ambos $p-1$$d$, de modo que, desde el $p$ es el menor factor primo de $d$, $9$ tiene orden de $1$$p=2$.

Ahora tenga en cuenta que$3=-1 \pmod 4$, de modo que si $a$ incluso $3^{a}+1=2 \pmod 4$.En consecuencia, $a$ $b$ no pueden ser ambas cosas, incluso, de lo contrario $ab=0 \pmod 4$ $3^{a}+1=2 \pmod 4$ lo cual es imposible si $ab|3^{a}+1$. Por lo $d$ no ha $2$ como un factor principal. Podemos obtener la deseada contradicción, mostrando que $d=1$.

Answer 2

Aquí es una idea inconclusa. Tal vez sea útil, tal vez no lo voy a publicar y cualquier persona es bienvenida a tratar de terminar o adaptarla.

---

Por supuesto, un número $n$ divide tanto a a $x$ $y$ si y sólo si $n$ divide $\gcd(x,y)$.

Suponer sin pérdida de generalidad que $b\geq a$, y escribir $b=qa+r$$0\leq r<a$. Observar que $$\begin{align*} \gcd(3^a+1,3^b+1)=\gcd(3^a+1,3^b-3^a)&=\gcd(3^a+1,3^{b-a}-1)\\ =\gcd(3^a+1,3^{b-a}+3^a)&=\gcd(3^a+1,3^{b-2a}+1)\\ &=\cdots\\ &=\gcd(3^a+1,3^r+(-1)^q) \end{align*}$$ De hecho, haciendo un argumento análogo, siempre tenemos $$\gcd(3^a\pm1,3^b\pm 1)=\gcd(3^a\pm1,3^r\pm 1)\qquad \text{(signs not intended to match)}$$ Por lo tanto, podemos concluir $$\gcd(3^a\pm 1,3^b\pm 1)=\gcd(3^a\pm1,3^{\gcd(a,b)}\pm 1)=\gcd(3^{\gcd(a,b)}\pm1,3^{\gcd(a,b)}\pm1)\\ =\begin{cases} 3^{\gcd(a,b)}\pm 1 & \text{if signs match},\\ 2 & \text{if signs don't match} \end{casos}$$ Supongamos que $\gcd(3^a+1,3^b+1)=3^{\gcd(a,b)}\pm 1$. De ahí a decir que esto es divisible por $ab$ significa $$3^{\gcd(a,b)}\equiv\pm1\bmod ab$$ Por lo tanto, el orden de $3$ $(\mathbb{Z}/ab\mathbb{Z})^\times$ divide $2\gcd(a,b)$. Por supuesto también se debe dividir $\varphi(ab)$... pero eso no es una contradicción, sin embargo.