求所有满足条件的正整数n：gcd(a,n)=1时2n²|(aⁿ-1)恒成立

让我们一步步拆解这个问题：找出所有正整数n，使得对任意与n互质的正整数a，2n²都能整除aⁿ - 1。

要满足2n² | aⁿ - 1，等价于同时满足两个子条件：

• mod 2的条件：对所有gcd(a,n)=1的a，aⁿ ≡ 1 mod 2。这自动成立，因为a必然是奇数，而奇数的任何次幂都是1 mod 2。
• mod n²的条件：对所有gcd(a,n)=1的a，aⁿ ≡ 1 mod n²。这是需要重点分析的核心条件。

如果n是奇数且大于1，设p是n的任意奇素因子。根据费马小定理，对所有与p互质的a，a^(p-1) ≡ 1 mod p；而题目要求aⁿ ≡ 1 mod p对所有这类a成立，这意味着p-1必须整除n。但p是奇素数，p-1是偶数，n是奇数——偶数不可能整除奇数，矛盾。

而n=1时，2*1²=2需要整除a-1对所有正整数a（因为gcd(a,1)=1恒成立），但取a=2时，2无法整除1，不满足条件。因此n必须是偶数，即n=2m，其中m是奇数。

此时2n²=8m²，条件转化为：对所有奇数且与m互质的a，需同时满足：

• mod 8的条件：奇数a的平方恒为1 mod 8，因此a^(2m)=(a²)m ≡ 1^m=1 mod 8，自动满足。
• mod m²的条件：对所有与m互质的a，a^(2m) ≡ 1 mod m²。这是我们需要聚焦的核心。

设m的素因子分解为m=∏p_i^k_i（p_i是奇素数，k_i≥1），对每个素因子p|m，需要满足两个约束：

1. mod p的约束：对所有与p互质的a，a^(2m) ≡1 mod p。由于Z_p^*（模p的乘法群）是循环群，阶为p-1，因此p-1必须整除2m。
2. mod p²的约束：对所有与p互质的a，a^(2m) ≡1 mod p²。根据费马小定理，a^(p-1)=1+pb_a（b_a是整数，且存在a使得b_a≢0 mod p，比如模p的原根）。因为p-1|2m，设2m=(p-1)t，则a^{(2m)=(1+pb_a)}t ≡1 + tpb_a mod p²。要让这个结果≡1 mod p²，必须tpb_a≡0 mod p²，即tb_a≡0 mod p。由于存在a使得b_a≢0 mod p，因此t必须被p整除，即p|2m/(p-1)。又因为p与p-1互质，且m是奇数，所以p|m。

我们从最小的可能值开始构造：

• n=2：m=1，无素因子，所有条件自动满足。验证：对任意奇数a，a²≡1 mod 8=2*2²，成立。
• n=6：m=3（奇素数）。检查约束：
  • p=3，p-1=2，2|2*3=6，满足mod p约束；
  • t=2m/(p-1)=6/2=3，3|3，满足mod p²约束。
    验证：对任意与6互质的a（奇数且不被3整除），a^6≡1 mod 72=2*6²，比如a=5时，5^6-1=15624，15624/72=217，整除。
• n=42：m=3*7（两个奇素数）。检查约束：
  • p=3：p-1=2|2*21=42，t=42/2=21，3|21，满足；
  • p=7：p-1=6|42，t=42/6=7，7|7，满足。
    验证：欧拉定理保证a^42≡1 mod 49，a^6≡1 mod9，结合mod8的条件，a^42≡1 mod 3528=2*42²，成立。
• n=1806：m=3743（三个奇素数）。检查约束：
  • p=3：p-1=2|2*903=1806，t=1806/2=903，3|903，满足；
  • p=7：p-1=6|1806，t=1806/6=301，7|301（301=7*43），满足；
  • p=43：p-1=42|1806，t=1806/42=43，43|43，满足mod43²约束。
    验证：a^1806=(a42)^{43≡(1+43b_a)}43≡1 mod43²，结合其他模条件，整体满足2*1806²|a^1806-1。

下一个可能的素因子p需要满足：p是素数，p-1整除237*43=1806，且p是未使用过的新素数。但1806的所有因子加1后，只有2、3、7、43是素数，均已被使用，没有新的素数可选。因此不存在更大的n。

所有满足条件的正整数n是：2, 6, 42, 1806

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