数论题

[TheMatrix]

n²+1如果不是素数的话，那么只能有4k+1类型的质因数。

注：trivially，n²+1如果是素数的话，只能是4k+1类型的素数。

注2：准确说应该是n²+1不能有4k+3类型的质因数。

[labi]

https://math.stackexchange.com/question ... f-form-4k1

[TheMatrix]

https://math.stackexchange.com/question ... f-form-4k1

Oh my god! 虽然是初等数论题 - 也不容易！

[TheMatrix]

https://math.stackexchange.com/question ... f-form-4k1

证明所有的4k+1素数，都是某n²+1的因子。

这个就没那么容易了。

[TheMatrix]

证明所有的4k+1素数，都是某n²+1的因子。

这个就没那么容易了。

这个也许不需要是素数，或者说放宽一点，任何4k+1的数，都是某n²+1的因子。

这应该就不难了。

[TheMatrix]

这个也许不需要是素数，或者说放宽一点，任何4k+1的数，都是某n²+1的因子。

这应该就不难了。

不行。还是需要素数。至少不能有4k+3的素因子。

[changbaihou]

证明所有的4k+1素数，都是某n²+1的因子。

这个就没那么容易了。

n=(2k)! 就行了吧。From威尔逊定理: p整除(p-1)!+1。

[bihai]

n²+1如果不是素数的话，那么只能有4k+1类型的质因数。

注：trivially，n²+1如果是素数的话，只能是4k+1类型的素数。

10?

[TheMatrix]

n=(2k)! 就行了吧。From威尔逊定理: p整除(p-1)!+1。

From威尔逊定理，有p=4k+1整除 (4k)!+1。
但是你的n=(2k)!，n²+1=(2k)!(2k)!+1。
好像不能说明p整除n²+1啊。

[TheMatrix]

10?

嗯。这个地方应该说n²+1不能有4k+3类型的素因子。

[TheMatrix]

再追加三个：

1，任何p=4k+1的素数，都存在正整数q<p，such that pq-1=n²。

2，任何正整数x，如果只有4k+1的素因数，那么都存在正整数 q<x，such that qx-1=n²。

3，trivially，n²+1不能整除4。所以问题2中的x变成4x的话就不成立了，但是2x是可以的 - 这是问题3。

这些问题不知道难度如何。可能不容易。

我再追加一个statement：前面三个问题中的q是唯一的。

也就是比如对于一个p=4k+1素数，只能找到唯一一个q<p，such that pq=n²+1。

有了前面的证明，这个应该不难吧。

[changbaihou]

From威尔逊定理，有p=4k+1整除 (4k)!+1。
但是你的n=(2k)!，n²+1=(2k)!(2k)!+1。
好像不能说明p整除n²+1啊。

Modulo p, (4k)!=(2k)!*(2k+1)...(4k)\equiv (2k)!*(-2k)(-(2k-1))...(-1)=(-1)^(2k)((2k)!)^2=((2k)!)^2

[changbaihou]

再追加三个：

1，任何p=4k+1的素数，都存在正整数q<p，such that pq-1=n²。

2，任何正整数x，如果只有4k+1的素因数，那么都存在正整数 q<x，such that qx-1=n²。

3，trivially，n²+1不能整除4。所以问题2中的x变成4x的话就不成立了，但是2x是可以的 - 这是问题3。

这些问题不知道难度如何。可能不容易。

有了你前面那个问题的答案后，1是trivially true; 从中国剩余定理，2和3也是对的。

[TheMatrix]

Modulo p, (4k)!=(2k)!*(2k+1)...(4k)\equiv (2k)!*(-2k)(-(2k-1))...(-1)=(-1)^(2k)((2k)!)^2=((2k)!)^2

哦。很好。

[TheMatrix]

有了你前面那个问题的答案后，1是trivially true; 从中国剩余定理，2和3也是对的。

哦？1怎么trivially true了？

[changbaihou]

哦？1怎么trivially true了？

Reducing n modulo p => There is an integer n\in [0, p-1] such that p|(n^2+1)=> there is positive integer q st pq-1=n^2 and q=(n^2+1)/p\leq ((p-1)^2+1)/p<p.

[TheMatrix]

Reducing n modulo p => There is an integer n\in [0, p-1] such that p|(n^2+1)=> there is positive integer q st pq-1=n^2 and q=(n^2+1)/p\leq ((p-1)^2+1)/p<p.

嗯。很好。

我也想到了。开始我也是考虑 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]

嗯。很好。

我也想到了。开始我也是考虑 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的倍数？中国剩余定理在这里怎么用？

从n² = -1 mod p的角度看，容易和群论联系起来。大概来说，就是群 Z_p^x 里找阶（order）等于4的元素。

[YWY]

有了你前面那个问题的答案后，1是trivially true; 从中国剩余定理，2和3也是对的。

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

[TheMatrix]

从n² = -1 mod p的角度看，容易和群论联系起来。大概来说，就是群 Z_p^x 里找阶（order）等于4的元素。

你这个，是回答我如下的问题吗？我没看出来联系：

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