数学竞赛每日一练 第22期解答

题目来源：2021.06「根源杯」初高数学衔接联考 二试第四题。

若 $m$，$n$ 为两个互素的正整数，求最大公约数

$$ \left(5^m+7^m,\ 5^n+7^n\right) $$

的所有可能值。

注． 原文引理中的结论印作 $(a^m-b^m,a^n-b^n)=a^{(m,n)}=b^{(m,n)}$，两个等号中的后者应为减号，即 $a^{(m,n)}-b^{(m,n)}$（否则结论显然不成立，如 $a=7$、$b=5$、$m=2$、$n=1$ 时左边为 $2$ 而右边为 $7=5$ 是荒谬的）。以下已按正确的结论转写，并把原文并列在一行内的公式分开、补全个别跳步。

解答 先证明如下引理。

引理. 设 $a,b,m,n\in\mathbb{N}^+$ 且 $ab\neq 1$，$(a,b)=1$。不妨设 $a\geq b$，$m\geq n$，则 $(a^m-b^m,\ a^n-b^n)=a^{(m,n)}-b^{(m,n)}$。

引理的证明． 对于 $x,y,k\in\mathbb{N}^+$，有恒等式

$$ x^k-y^k=(x-y)\left(x^{k-1}+x^{k-2}y+\cdots+y^{k-1}\right). $$

因为 $(m,n)$ 同时整除 $m$ 与 $n$，在上式中取 $x=a^{(m,n)}$，$y=b^{(m,n)}$，$k=\frac{m}{(m,n)}$（或 $\frac{n}{(m,n)}$）可知

$$ a^{(m,n)}-b^{(m,n)}\mid a^m-b^m,\qquad a^{(m,n)}-b^{(m,n)}\mid a^n-b^n. $$

从而

$$ a^{(m,n)}-b^{(m,n)}\mid (a^m-b^m,\ a^n-b^n). $$

为证两者相等，只须再证明

$$ (a^m-b^m,\ a^n-b^n)\mid a^{(m,n)}-b^{(m,n)}. $$

设 $c=(a^m-b^m,a^n-b^n)$，由 $(a,b)=1$ 知 $(b,c)=1$。设 $d=(m,n)$。由 Bezout 定理，存在整数 $u_0,v_0$ 使 $u_0m+v_0n=d$；把 $u_0$ 换成 $u_0+kn$、$v_0$ 换成 $v_0-km$（$k$ 为任意整数）不改变等式，故可选取正整数 $u,v$，使

$$ um-vn=(m,n)=d. $$

由 $c\mid a^n-b^n$ 有 $c\mid a^{vn}-b^{vn}$，从而

$$ c\mid a^{d}\left(a^{vn}-b^{vn}\right)=a^{um}-a^{d}\cdot b^{vn}. $$

而由 $c\mid a^m-b^m$ 又有 $c\mid a^{um}-b^{um}$。两式相减得 $c\mid\left(a^{d}-b^{d}\right)\cdot b^{vn}$。又 $(b,c)=1$，从而 $c\mid a^{d}-b^{d}$，即 $(a^m-b^m,\ a^n-b^n)\mid a^{(m,n)}-b^{(m,n)}$。于是 $(a^m-b^m,a^n-b^n)=a^{(m,n)}-b^{(m,n)}$，引理证毕。$\square$

回到原题。因为

$$ 5^m+7^m\mid (7^m-5^m)(7^m+5^m)=7^{2m}-5^{2m},\qquad 5^n+7^n\mid 7^{2n}-5^{2n}, $$

所以

$$ \left(5^m+7^m,\ 5^n+7^n\right)\mid \left(7^{2m}-5^{2m},\ 7^{2n}-5^{2n}\right). $$

对 $a=7$，$b=5$ 用引理，并注意 $(2m,2n)=2(m,n)=2$（$m$，$n$ 互素），得

$$ \left(7^{2m}-5^{2m},\ 7^{2n}-5^{2n}\right)=7^{2(m,n)}-5^{2(m,n)}=7^2-5^2=24. $$

所以 $\left(5^m+7^m,\ 5^n+7^n\right)\mid 24$。

当 $m$，$n$ 均为奇数时，由因式分解

$$ 5^m+7^m=12\left(5^{m-1}-5^{m-2}\cdot 7+\cdots+7^{m-1}\right),\qquad 5^n+7^n=12\left(5^{n-1}-5^{n-2}\cdot 7+\cdots+7^{n-1}\right) $$

得 $12\mid(5^m+7^m,5^n+7^n)$。又对 $k\in\mathbb{Z}^+$ 有

$$ 5^{2k+1}\equiv 5\pmod 8,\qquad 7^{2k+1}\equiv 7\equiv -1\pmod 8, $$

故 $5^m+7^m\equiv 5+7=12\equiv 4\pmod 8$，即 $8\nmid 5^m+7^m$，从而 $8\nmid(5^m+7^m,5^n+7^n)$。由 $12\mid(5^m+7^m,5^n+7^n)\mid 24$ 知 $(5^m+7^m,5^n+7^n)$ 只能是 $12$ 或 $24$，而 $8\mid 24$ 与 $8\nmid(5^m+7^m,5^n+7^n)$ 矛盾，故此时 $(5^m+7^m,\ 5^n+7^n)=12$。

当 $m$，$n$ 中有一个为偶数时，不妨设 $m$ 为偶数、$n$ 为奇数。因为 $5^m\equiv 1\pmod 4$，$7^m\equiv 1\pmod 4$，所以 $5^m+7^m\equiv 2\pmod 4$，即 $4\nmid 5^m+7^m$；又 $5^m\equiv 1\pmod 3$，$7^m\equiv 1\pmod 3$，所以 $5^m+7^m\equiv 2\pmod 3$，即 $3\nmid 5^m+7^m$。于是 $4\nmid(5^m+7^m,5^n+7^n)$，$3\nmid(5^m+7^m,5^n+7^n)$。又 $5^m+7^m$ 与 $5^n+7^n$ 都是偶数，故 $(5^m+7^m,5^n+7^n)$ 是 $24$ 的偶因子，且不被 $3$ 或 $4$ 整除，只能是 $2$。即此时 $(5^m+7^m,\ 5^n+7^n)=2$。

综上所述，$(5^m+7^m,5^n+7^n)$ 的可能值为 $2$ 或 $12$（当 $m$，$n$ 均为奇数时取 $12$，否则取 $2$）。