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).
YWY 写了： ↑1月 13, 2024, 11:18 am
同意。如果考虑细节的话，那么在用中国剩余定理之前还要解决形式为p = 4k+1的素数的方幂的形况。类似于上面的链接，可以通过考虑模掉(4k+1)r得到的乘法群（阶数为(4k+1)r的totient number的循环群），这个totient number被4整除，所以能找到阶数为4的元素（其平方等于 -1 mod (4k+1)r）。
That's right, you need to consider p^k|(x^2+1) for a general power p^k before using CRT. Since p>2 and x^2+1 has only degree 2, by Hensel's Lemma there is a one-to-one correspondence between the (two) solutions to x^2+1\equiv 0 \pmod{p^k} and the solutions to x^2+1\equiv 0 \pmod{p}.
changbaihou 写了： ↑1月 13, 2024, 12:15 pm
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).
wow，这里不少东西啊 - Hensel's Lemma, Chinese Remainder Theorem.
不过中国剩余定理这里我还有点疑问。wiki上写的是：
x-r1=0 (mod p1)
x-r2=0 (mod p2)
x-r3=0 (mod p3)
那么存在x satisfy both mod p1p2p3。
你这里换成了f(x)=x2+1。这是二次的啊。这行吗？
那么当素数 p=4k+1 时，Zpx 是阶数为 4k 的循环群, 所以能够找到阶数为4的元素，而且（不多不少）有两个阶数为4的元素（满足n4 = 1 mod p 但 n2 不等于 1 mod p，所以n2 = -1 mod p，也就是p整除n2 + 1），如果一个元素是n，那么另外一个就是n3 = -n mod p，他们两互为对方的3次方（mod p，做为Zpx中的元素），这两个元素（正负n）的平方相等。所以满足 pq = n2 + 1 mod p 的 q mod 有（至多）两个解，而且两个不同解确实会发生，比如5 x 1 = 5 和 5 x 2 = 10。这回答了你前面问过的唯一性。
YWY 写了： ↑1月 15, 2024, 11:16 am
当 p 是素数时，Zpx 是阶数为 p-1 的循环群。
那么当素数 p=4k+1 时，Zpx 是阶数为 4k 的循环群, 所以能够找到阶数为4的元素，而且（不多不少）有两个阶数为4的元素（满足n4 = 1 mod p 但 n2 不等于 1 mod p，所以n2 = -1 mod p，也就是p整除n2 + 1），如果一个元素是n，那么另外一个就是n3 = -n mod p，他们两互为对方的3次方（mod p，做为Zpx中的元素），这两个元素（正负n）的平方相等。所以满足 pq = n2 + 1 mod p 的 q mod 有（至多）两个解，而且两个不同解确实会发生，比如5 x 1 = 5 和 5 x 2 = 10。这回答了你前面问过的唯一性。
YWY 写了： ↑1月 15, 2024, 11:16 am
当 p 是素数时，Zpx 是阶数为 p-1 的循环群。
那么当素数 p=4k+1 时，Zpx 是阶数为 4k 的循环群, 所以能够找到阶数为4的元素，而且（不多不少）有两个阶数为4的元素（满足n4 = 1 mod p 但 n2 不等于 1 mod p，所以n2 = -1 mod p，也就是p整除n2 + 1），如果一个元素是n，那么另外一个就是n3 = -n mod p，他们两互为对方的3次方（mod p，做为Zpx中的元素），这两个元素（正负n）的平方相等。所以满足 pq = n2 + 1 mod p 的 q mod 有（至多）两个解，而且两个不同解确实会发生，比如5 x 1 = 5 和 5 x 2 = 10。这回答了你前面问过的唯一性。
