西班牙地区奥数题：求满足条件的正整数集合交集

问题梳理 #

先把两个相关问题明确下来：

• 问题1：设$A\subset\Bbb N$，满足对任意$a\in A$、$b\in\Bbb N$，存在整数$c$使得$a+bc$为完全平方数，求$A\cap{1,2,\dots,2018}$。
• 问题2（西班牙本地奥数第一题）：设$\Bbb N^$为正整数集，$A$是$\Bbb N^$的子集，满足对任意$a\in A$、$b\in\Bbb N^*$，存在正整数$c$使得$a+bc$为完全平方数，求$B=A\cap{1,2,\ldots,2018}$。

提问者已经观察到$1^2,22,\dots,44^{2$（其中$44}2=1936$，$45^2=2025>2018$）都属于集合$B$，但对条件$a\equiv m^2\pmod b$的理解和应用存在困惑，接下来我们一步步拆解。

核心等价转化 #

题目中的条件可以翻译成：对给定的$a$，无论取哪个正整数$b$，都存在某个整数$m$，使得$m^2 - a$能被$b$整除——也就是$a$必须是模任意正整数$b$的二次剩余。

这时候关键结论来了：只有完全平方数才能满足这个条件，我们可以从正反两方面验证：

1. 完全平方数满足条件 #

假设$a=n^2$（$n$是正整数）：

• 若允许$c=0$（对应问题1的$\Bbb N$包含0的情况），直接取$m=n$，则$a+bc=n^2+b\cdot0=n2$，本身就是平方数。
• 若要求$c$是正整数（对应问题2的$\Bbb N^*$），我们可以取$m=n+kb$（$k$为正整数），展开后：

  m^2 = (n+kb)^2 = n^2 + 2nkb + k²b²
  

  那么$m^2 - a = b(2nk + k²b)$，令$c=2nk + k²b$，这显然是正整数，完美满足$a+bc=m^2$的要求。

2. 非完全平方数不满足条件 #

假设$a$不是完全平方数，那么必然存在某个素数$p$，它在$a$的素因子分解中的指数是奇数（比如$a=p^{2k+1}\cdot t$，其中$t$与$p$互质）。

现在取$b=p^{{k+1}$，我们看是否存在$m$使得$m}2\equiv a\pmod{p^{k+1}}$：
把$m$写成$p^s\cdot m'$（$m'$与$p$互质），则$m^2=p{2s}\cdot m'^{2$，它模$p}{k+1}$的$p$指数是$2s$（偶数），而$a$模$p^{k+1}$的$p$指数是$2k+1$（奇数），偶数不可能等于奇数，矛盾。这说明不存在这样的$m$，自然也找不到对应的$c$，所以非平方数不属于$A$。

最终结论 #

不管是问题1还是问题2，$A\cap{1,2,\dots,2018}$的元素就是所有不超过2018的完全平方数，也就是：
$$1^2,22,3^2,\dots,442$$
你之前观察到的这部分完全正确，而且这就是集合的全部元素，没有其他数符合要求。

关于$a\equiv m^2\pmod b$的困惑解答 #

这个同余式的核心是要求$a$在任意模$b$下都能找到对应的二次剩余$m$，而只有完全平方数能做到这一点。举个直观的例子：

• 取$a=2$（非平方数），选$b=3$，模3的二次剩余只有0和1，2不在其中，所以$2+3c$模3永远是2，不可能是平方数（平方数模3只能是0或1），因此2不属于$A$。
• 再取$a=3$（非平方数），选$b=4$，模4的二次剩余是0和1，3不在其中，$3+4c$模4永远是3，也不可能是平方数，所以3也不属于$A$。

这样是不是就把这个同余条件的意义和应用搞清楚了？

内容的提问来源于stack exchange，提问作者ajotatxe