Question

求有序对 $(m, n)$ 的个数，使得 $m$ 和 $n$ 是集合 $\{1, 2, \ldots, 30\}$ 中的正整数，且 $2^m + 1$ 与 $2^n - 1$ 的最大公约数不是 $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.$

答案

答案：295

知识点：乘法阶最大公约数 2的幂

难度评级：2920

解答：

假设奇素数 $p$ 同时整除 $2^m + 1$ 和 $2^n - 1$ 。由 $2^m \equiv -1 \pmod p$ 可知， $2$ 模 $p$ 的阶整除 $2m$ 但不整除 $m$ ，因此这个阶中因子 $2$ 的个数恰好比 $m$ 中多一个。这个阶也整除 $n$ ，所以 $n$ 中因子 $2$ 的个数必须严格多于 $m$ 中的个数。记 $v_2$ 为因子 $2$ 的个数，则需要 $v_2(n) \gt v_2(m)$ 。

反过来，若 $v_2(n) \gt v_2(m)$ ，设 $g = \gcd(m, n)$ 。则 $v_2(g) = v_2(m)$ ，所以 $m/g$ 为奇数，且 $2^g + 1 \mid 2^m + 1$ ；同时 $2g \mid n$ ，所以 $2^g + 1 \mid 2^{2g} - 1 \mid 2^n - 1$ 。因此最大公约数大于 $1$ 当且仅当 $v_2(n) \gt v_2(m)$ 。

在 $1, \ldots, 30$ 中，满足 $v_2 = 0, 1, 2, 3, 4$ 的数的个数分别为 $15, 8, 4, 2, 1$ 。满足 $v_2(m) \lt v_2(n)$ 的有序对数为 $\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 第 9 题

答案：295

难度评级：2920

解答：

其他年份的第 9 题