新未名空间

TheMatrix 写了： 2024年 1月 13日 08:59 嗯。很好。

我也想到了。开始我也是考虑 p | (n²+1)的问题，这个形式容易看出 p | (n+kp)²+1，所以n可以取(0,p)之间的整数。后来我突然把问题写成 mp-1=n²的形式。然后我就看不出来了。

不过第2,3个问题我还是没想出怎么就成立。现在可以假设 p|n²+1，q|m²+1，怎么找到k使得k²+1是pq的倍数？中国剩余定理在这里怎么用？

YWY 写了： 2024年 1月 13日 11:18 同意。如果考虑细节的话，那么在用中国剩余定理之前还要解决形式为p = 4k+1的素数的方幂的形况。类似于上面的链接，可以通过考虑模掉(4k+1)^r得到的乘法群（阶数为(4k+1)^r的totient number的循环群），这个totient number被4整除，所以能找到阶数为4的元素（其平方等于 -1 mod (4k+1)^r）。

changbaihou 写了： 2024年 1月 12日 22:52 有了你前面那个问题的答案后，1是trivially true; 从中国剩余定理，2和3也是对的。

changbaihou 写了： 2024年 1月 13日 12:15 f(x)=x^2+1\equiv 0\pmod{p} is solvable ==> for any k\in N, f(x)=x^2+1\equiv 0\pmod{p^k} is solvable (Hensel's Lemma); Now, if N={p_1}^{k_1}...{p_s}^{k_s} with the p_j's being distinct primes \equiv 1\pmod{4}, we have f(x)\equiv 0\pmod{N} solvable (Chinese Remainder Theorem). Same as before, there is an n\in [0, N] such that N\mid{n^2+1},==>.....

For this n\in [0, N-1] satisfying N|(n^1+1), we have 2N|(n^1+1) if n is odd; and 2N|((n+N)^2+1 if n is even (where you still have 0<n+N<2N).

changbaihou 写了： 2024年 1月 12日 22:52 有了你前面那个问题的答案后，1是trivially true; 从中国剩余定理，2和3也是对的。

YWY 写了： 2024年 1月 13日 11:05 从n² = -1 mod p的角度看，容易和群论联系起来。大概来说，就是群 Z_p^x 里找阶（order）等于4的元素。

TheMatrix 写了： 2024年 1月 13日 11:50 你这个，是回答我如下的问题吗？我没看出来联系：

TheMatrix 写了： 2024年 1月 13日 12:59 wow，这里不少东西啊 - Hensel's Lemma, Chinese Remainder Theorem.

不过中国剩余定理这里我还有点疑问。wiki上写的是：
x-r₁=0 (mod p₁)
x-r₂=0 (mod p₂)
x-r₃=0 (mod p₃)
那么存在x satisfy both mod p₁p₂p₃。
你这里换成了f(x)=x²+1。这是二次的啊。这行吗？

FGH 写了： 2024年 1月 13日 16:19 2和4k+1类型的素数在复整数Z里不是真正的素数。
而4k+3类型的素数则是Z里的真正素数。
比如2=(1+i)(1-i), 5=(2+i)(2-i), 13=(3+2i)(3-2i), 17=(4+i)(4-i).
把n^2+1在Z里分解成(n+i)(n-i)。因为n+i和n-i不可能被4k+3类型的素数整除，
所以它们的Z里的素因子都是非实数，也就是形如a+bi，
满足a^2+b^2是4k+1类型的素数。

YWY 写了： 2024年 1月 13日 16:07 你上面的p_i不需要都是素数，只需两两互质（最大公约数为1）即可。

再就是，一次或者二次，在这里是无关的。按前面说讨论，模掉每一个型为4k+1的素数的方幂（记作q_i），我们都能找到一个满足条件相应的n_i使得q_i整除n_i²+1；由中国剩余定理，就能找到整数n使得n = n_i mod q_i，这个n就满足你的最终条件。

FGH 写了： 2024年 1月 13日 16:19 2和4k+1类型的素数在复整数Z[ i ]里不是真正的素数。
而4k+3类型的素数则是Z[ i ]里的真正素数。
比如2=(1+i)(1-i), 5=(2+i)(2-i), 13=(3+2i)(3-2i), 17=(4+i)(4-i).
把n^2+1在Z[ i ]里分解成(n+i)(n-i)。因为n+i和n-i不可能被4k+3类型的素数整除，
所以它们的Z[ i ]里的素因子都是非实数，也就是形如a+bi，
满足a^2+b^2是4k+1类型的素数。

YWY 写了： 2024年 1月 13日 11:05 从n² = -1 mod p的角度看，容易和群论联系起来。大概来说，就是群 Z_p^x 里找阶（order）等于4的元素。

YWY 写了： 2024年 1月 13日 11:05 从n² = -1 mod p的角度看，容易和群论联系起来。大概来说，就是群 Z_p^x 里找阶（order）等于4的元素。

TheMatrix 写了： 2024年 1月 15日 09:47 嗯。对。在Z_p=Z/pZ中考虑这个问题更清楚。

也就是研究n²+1=0在Z/pZ中是否有解的问题。p=4k+1的时候有解，这个的证明应该就是changbaihou给出的那个方法。而且有解的话就是成对出现。

YWY 写了： 2024年 1月 15日 11:16 当 p 是素数时，Z_p^x 是阶数为 p-1 的循环群。

那么当素数 p=4k+1 时，Z_p^x 是阶数为 4k 的循环群, 所以能够找到阶数为4的元素，而且（不多不少）有两个阶数为4的元素（满足n⁴ = 1 mod p 但 n² 不等于 1 mod p，所以n² = -1 mod p，也就是p整除n² + 1），如果一个元素是n，那么另外一个就是n³ = -n mod p，他们两互为对方的3次方（mod p，做为Z_p^x中的元素），这两个元素（正负n）的平方相等。所以满足 pq = n² + 1 mod p 的 q mod 有（至多）两个解，而且两个不同解确实会发生，比如5 x 1 = 5 和 5 x 2 = 10。这回答了你前面问过的唯一性。

群论的方法只能证出n的存在，但没给出具体值。changbaihou的方法利用威尔逊引理，好处是明确地给出了n的具体值。

YWY 写了： 2024年 1月 15日 11:16 当 p 是素数时，Z_p^x 是阶数为 p-1 的循环群。

那么当素数 p=4k+1 时，Z_p^x 是阶数为 4k 的循环群, 所以能够找到阶数为4的元素，而且（不多不少）有两个阶数为4的元素（满足n⁴ = 1 mod p 但 n² 不等于 1 mod p，所以n² = -1 mod p，也就是p整除n² + 1），如果一个元素是n，那么另外一个就是n³ = -n mod p，他们两互为对方的3次方（mod p，做为Z_p^x中的元素），这两个元素（正负n）的平方相等。所以满足 pq = n² + 1 mod p 的 q mod 有（至多）两个解，而且两个不同解确实会发生，比如5 x 1 = 5 和 5 x 2 = 10。这回答了你前面问过的唯一性。

群论的方法只能证出n的存在，但没给出具体值。changbaihou的方法利用威尔逊引理，好处是明确地给出了n的具体值。

TheMatrix 写了： 2024年 1月 15日 12:02 嗯。群论的方法去粗取精了。

当p是4k+1素数因子的合数时，好像也可以用二次互反定理证明吧。