Question

Halle el número de pares ordenados $(m, n)$ tales que $m$ y $n$ son enteros positivos del conjunto $\{1, 2, \ldots, 30\}$ y el máximo común divisor de $2^m + 1$ y $2^n - 1$ no es $1$ .

Find the number of ordered pairs $(m, n)$ such that $m$ and $n$ are positive integers in the set $\{1, 2, \ldots, 30\}$ and the greatest common divisor of $2^m + 1$ and $2^n - 1$ is not $1.$

Respuesta

Solución:

Supongamos que un primo impar $p$ divide tanto a $2^m + 1$ como a $2^n - 1$ . De $2^m \equiv -1 \pmod p$ , el orden de $2$ módulo $p$ divide a $2m$ pero no a $m$ , así que el orden contiene exactamente un factor de $2$ más que $m$ . El orden también divide a $n$ , así que $n$ debe contener estrictamente más factores de $2$ que $m$ : escribiendo $v_2$ para el número de factores de $2$ , necesitamos $v_2(n) \gt v_2(m)$ .

Recíprocamente, si $v_2(n) \gt v_2(m)$ , sea $g = \gcd(m, n)$ . Entonces $v_2(g) = v_2(m)$ , así que $m/g$ es impar y $2^g + 1 \mid 2^m + 1$ ; además $2g \mid n$ , así que $2^g + 1 \mid 2^{2g} - 1 \mid 2^n - 1$ . Por lo tanto el máximo común divisor supera $1$ exactamente cuando $v_2(n) \gt v_2(m)$ .

Entre $1, \ldots, 30$ , las cantidades de números con $v_2 = 0, 1, 2, 3, 4$ son $15, 8, 4, 2, 1$ . El número de pares con $v_2(m) \lt v_2(n)$ es $\begin{aligned} &15 \cdot 15 + 8 \cdot 7 + 4 \cdot 3 + 2 \cdot 1 \\ &= 225 + 56 + 12 + 2 = 295. \end{aligned}$

Suppose an odd prime $p$ divides both $2^m + 1$ and $2^n - 1.$ From $2^m \equiv -1 \pmod p,$ the order of $2$ modulo $p$ divides $2m$ but not $m,$ so the order contains exactly one more factor of $2$ than $m$ does. The order also divides $n,$ so $n$ must contain strictly more factors of $2$ than $m:$ writing $v_2$ for the number of factors of $2,$ we need $v_2(n) \gt v_2(m).$

Conversely, if $v_2(n) \gt v_2(m),$ let $g = \gcd(m, n).$ Then $v_2(g) = v_2(m),$ so $m/g$ is odd and $2^g + 1 \mid 2^m + 1;$ also $2g \mid n,$ so $2^g + 1 \mid 2^{2g} - 1 \mid 2^n - 1.$ Hence the gcd exceeds $1$ exactly when $v_2(n) \gt v_2(m).$

Among $1, \ldots, 30$ the counts of numbers with $v_2 = 0, 1, 2, 3, 4$ are $15, 8, 4, 2, 1.$ The number of pairs with $v_2(m) \lt v_2(n)$ is $\begin{aligned} &15 \cdot 15 + 8 \cdot 7 + 4 \cdot 3 + 2 \cdot 1 \\ &= 225 + 56 + 12 + 2 = 295. \end{aligned}$

2021 AIME II Problema 9

Solución:

El Problema 9 en otros años