x*****p
发帖数: 1707 | 1 大家做个题吧。素数除了2以外全是奇素数，那就可分成两种类型。一种是4k+1型的，
如5, 13, 17, 29；一种是4k+3型的，如3, 7, 11, 19。请证明这两种类型的素数都有
无穷多个。 |
u*****n
发帖数: 3277 | 2 费话，所有素数要不是4k+1要不是4k+3。当然是无穷多个。
【在 x*****p 的大作中提到】
: 大家做个题吧。素数除了2以外全是奇素数，那就可分成两种类型。一种是4k+1型的，
: 如5, 13, 17, 29；一种是4k+3型的，如3, 7, 11, 19。请证明这两种类型的素数都有
: 无穷多个。
|
I*********t
发帖数: 5258 | 3 不一定，可能其中一种只有有限多个，这个命题要证否这个可能。
【在 u*****n 的大作中提到】
: 费话，所有素数要不是4k+1要不是4k+3。当然是无穷多个。
|
x*****p
发帖数: 1707 | 4 文科生吧。
当素数很大的时候，可能只剩下4k+1类型的无穷个素数，不再发现新的4k+3类型的素数
了。
【在 u*****n 的大作中提到】
: 费话，所有素数要不是4k+1要不是4k+3。当然是无穷多个。
|
f*******i
发帖数: 1049 | 5 http://en.wikipedia.org/wiki/Dirichlet's_theorem_on_arithm
【在 x*****p 的大作中提到】
: 大家做个题吧。素数除了2以外全是奇素数，那就可分成两种类型。一种是4k+1型的，
: 如5, 13, 17, 29；一种是4k+3型的，如3, 7, 11, 19。请证明这两种类型的素数都有
: 无穷多个。
|
x*****p
发帖数: 1707 | 6 这不是专业数学论坛，只需要用中学的初等数学的方法就可以证明的。也就是说，文科
也能看懂的法子。
【在 f*******i 的大作中提到】
: http://en.wikipedia.org/wiki/Dirichlet's_theorem_on_arithm
|
f*******i
发帖数: 1049 | 7 最简单的证明要用Dirichlet L-函数,这是黎曼zeta函数的推广.
后来有初等证明,但是用得奇技淫巧很多,更难懂
【在 x*****p 的大作中提到】
: 这不是专业数学论坛，只需要用中学的初等数学的方法就可以证明的。也就是说，文科
: 也能看懂的法子。
|
x*****p
发帖数: 1707 | 8 对于4k+3的类型，不需要高深的法子，只需要以前的反证法即可。但构造的时候有点技
巧罢了。
【在 f*******i 的大作中提到】
: 最简单的证明要用Dirichlet L-函数,这是黎曼zeta函数的推广.
: 后来有初等证明,但是用得奇技淫巧很多,更难懂
|
b******5
发帖数: 1415 | 9 2*2*3*5*7*....*N + 1 for 4k+1
2*2*5*7*11*.....*N + 3 for 4k+3
???
【在 x*****p 的大作中提到】
: 对于4k+3的类型，不需要高深的法子，只需要以前的反证法即可。但构造的时候有点技
: 巧罢了。
|
d******k
发帖数: 4295 | 10 不需要复杂的技巧，和证明素数无穷差不多。
假设4k+3的素数是有限个，
P_1，P_2,...P_K,
N=P_1*P_2*...*P_K
N+1,N+3都是素数，必有一个是4k+3.
【在 x*****p 的大作中提到】
: 对于4k+3的类型，不需要高深的法子，只需要以前的反证法即可。但构造的时候有点技
: 巧罢了。
|
|
|
m**x
发帖数: 8454 | 11 no, there can be prime larger than N. because even if 4k+1 is assumed finite
,
4k+3 can be infinite. or vice versa.
【在 b******5 的大作中提到】
: 2*2*3*5*7*....*N + 1 for 4k+1
: 2*2*5*7*11*.....*N + 3 for 4k+3
: ???
|
m**x
发帖数: 8454 | 12 I don't think so. why N+1,N+3都是素数? N+1, N+3明明都是偶数。
【在 d******k 的大作中提到】
: 不需要复杂的技巧，和证明素数无穷差不多。
: 假设4k+3的素数是有限个，
: P_1，P_2,...P_K,
: N=P_1*P_2*...*P_K
: N+1,N+3都是素数，必有一个是4k+3.
|
a***e
发帖数: 27968 | 13 twin prime N+1, N+3?
【在 d******k 的大作中提到】
: 不需要复杂的技巧，和证明素数无穷差不多。
: 假设4k+3的素数是有限个，
: P_1，P_2,...P_K,
: N=P_1*P_2*...*P_K
: N+1,N+3都是素数，必有一个是4k+3.
|
m**x
发帖数: 8454 | 14 先证明4k+1无限：
假设4k+1有限，为K个。则N=P_1*P_2*...*P_K+4
N是4k+1类型的素数，因为：
1) N除以4余1
2）4k+3的素数不能整除N因为 1)
3）4k+1的素数不能整除N因为4不能被4k+1整除而P_1*P_2*...*P_K能 |
c**n
发帖数: 5275 | 15
5+4=9=3*3...
【在 m**x 的大作中提到】
: 先证明4k+1无限：
: 假设4k+1有限，为K个。则N=P_1*P_2*...*P_K+4
: N是4k+1类型的素数，因为：
: 1) N除以4余1
: 2）4k+3的素数不能整除N因为 1)
: 3）4k+1的素数不能整除N因为4不能被4k+1整除而P_1*P_2*...*P_K能
|
m**x
发帖数: 8454 | 16 文科生和反例又出现了
【在 c**n 的大作中提到】
:
: 5+4=9=3*3...
|
c**n
发帖数: 5275 | 17
对，本人作为文科生和民科代表指出逻辑缜密的理科生的漏洞，承让。
【在 m**x 的大作中提到】
: 文科生和反例又出现了
|
d******k
发帖数: 4295 | 18 恩，刚脑子进水了。
光想着假设由有限个4k+3素数构造一对数N+1，N+3,因为这一对数不能被有限个素数整
除，而推出他们都是素数，忘了还有无数个4k+1个素数可以当因子。
似乎这个问题不是那么容易用高中数学方法来征明。
【在 m**x 的大作中提到】
: I don't think so. why N+1,N+3都是素数? N+1, N+3明明都是偶数。
|
c****n
发帖数: 1646 | 19 文科生和反例又出现了
4K+1: 5,13,17,29
5*13*17*29+4=32049=3*3*3*1187
3=4*0+3,1187=296*4+3
【在 m**x 的大作中提到】
: 先证明4k+1无限：
: 假设4k+1有限，为K个。则N=P_1*P_2*...*P_K+4
: N是4k+1类型的素数，因为：
: 1) N除以4余1
: 2）4k+3的素数不能整除N因为 1)
: 3）4k+1的素数不能整除N因为4不能被4k+1整除而P_1*P_2*...*P_K能
|
m**x
发帖数: 8454 | 20 再证明4k+3无限：
假设4k+3有限，为K个。如K为奇数则N=P_1*P_2*...*P_K+4，若K为偶数则N=7*P_1*P_2*
...*P_K+4
N是4k+3类型的素数，因为：
1) N除以4余3 (至于为什么，不和文科生讨论）
2）4k+1的素数不能整除N因为 1)
3）4k+3的素数不能整除N因为4不能被4k+3整除而N－4能 |
|
|
c**n
发帖数: 5275 | 21
杀鸡焉用宰牛刀啊。。。
【在 c****n 的大作中提到】
: 文科生和反例又出现了
: 4K+1: 5,13,17,29
: 5*13*17*29+4=32049=3*3*3*1187
: 3=4*0+3,1187=296*4+3
|
m**x
发帖数: 8454 | 22 文科生这次别凑热闹了吧，本人可没有给素数下定义哦， 我声明一下用的是素数的性
质。承让。 |
c**n
发帖数: 5275 | 23
2*
理科生你好！
3*7*11+4=235。。。
理科生再见！
【在 m**x 的大作中提到】
: 再证明4k+3无限：
: 假设4k+3有限，为K个。如K为奇数则N=P_1*P_2*...*P_K+4，若K为偶数则N=7*P_1*P_2*
: ...*P_K+4
: N是4k+3类型的素数，因为：
: 1) N除以4余3 (至于为什么，不和文科生讨论）
: 2）4k+1的素数不能整除N因为 1)
: 3）4k+3的素数不能整除N因为4不能被4k+3整除而N－4能
|
n*****b
发帖数: 2235 | 24 这次的反例是对的
你的4k+1证明里第(2)条有点问题
【在 m**x 的大作中提到】
: 文科生和反例又出现了
|
b***y
发帖数: 14281 | 25 Easy.
By Yitang Zhang's Theorem, (to be completed soon), there are infinitely many
pairs of prime numbers that differ by 2. Therefore, there are infinitely
many prime numbers taking both the forms of 4k+1 and 4k+3.
End of proof. |
m**x
发帖数: 8454 | 26 这次还真栽了
【在 n*****b 的大作中提到】
: 这次的反例是对的
: 你的4k+1证明里第(2)条有点问题
|
n*****b
发帖数: 2235 | 27 这个反例不对
打回去重新找
【在 c**n 的大作中提到】
:
: 2*
: 理科生你好！
: 3*7*11+4=235。。。
: 理科生再见！
|
c**n
发帖数: 5275 | 28
235是4k+3类型的素数？
【在 n*****b 的大作中提到】
: 这个反例不对
: 打回去重新找
|
n*****b
发帖数: 2235 | 29 反例看来也不无是处 :)
【在 m**x 的大作中提到】
: 这次还真栽了
|
n*****b
发帖数: 2235 | 30 235 = 5 * 47
你用了47
但你的假设里没有47这个4k+3类型的素数
【在 c**n 的大作中提到】
:
: 235是4k+3类型的素数？
|
|
|
m**x
发帖数: 8454 | 31 谢谢指出并向你和carbon道歉, 是我不对。
【在 c**n 的大作中提到】
:
: 235是4k+3类型的素数？
|
b***y
发帖数: 14281 | 32 其实不如3*7+4=25干脆。
【在 n*****b 的大作中提到】
: 235 = 5 * 47
: 你用了47
: 但你的假设里没有47这个4k+3类型的素数
|
c**n
发帖数: 5275 | 33
他原文里的第二点是怎么说的？他说这个数无法被4k+1类型的素数整除
【在 n*****b 的大作中提到】
: 235 = 5 * 47
: 你用了47
: 但你的假设里没有47这个4k+3类型的素数
|
c**n
发帖数: 5275 | 34
这种情况他用的是3*7*7+4
【在 b***y 的大作中提到】
: 其实不如3*7+4=25干脆。
|
n*****b
发帖数: 2235 | 35 你这个没乘7
【在 b***y 的大作中提到】
: 其实不如3*7+4=25干脆。
|
m**x
发帖数: 8454 | 36 to be completed soon...
many
【在 b***y 的大作中提到】
: Easy.
: By Yitang Zhang's Theorem, (to be completed soon), there are infinitely many
: pairs of prime numbers that differ by 2. Therefore, there are infinitely
: many prime numbers taking both the forms of 4k+1 and 4k+3.
: End of proof.
|
n*****b
发帖数: 2235 | 37 你是对的
他原文说得不准确
我自动把证明修正了一下
把(2)改成了 这个数无法分解成4k+1类型的素数之积
【在 c**n 的大作中提到】
:
: 这种情况他用的是3*7*7+4
|
b***y
发帖数: 14281 | 38 I see. Didn't pay attention I suppose.
【在 c**n 的大作中提到】
:
: 这种情况他用的是3*7*7+4
|
d******k
发帖数: 4295 | 39 第二点不对，感觉假设有限然后构造素数的简单方法无法证明这个命题
2*
【在 m**x 的大作中提到】
: 再证明4k+3无限：
: 假设4k+3有限，为K个。如K为奇数则N=P_1*P_2*...*P_K+4，若K为偶数则N=7*P_1*P_2*
: ...*P_K+4
: N是4k+3类型的素数，因为：
: 1) N除以4余3 (至于为什么，不和文科生讨论）
: 2）4k+1的素数不能整除N因为 1)
: 3）4k+3的素数不能整除N因为4不能被4k+3整除而N－4能
|
n*****b
发帖数: 2235 | 40 参考我上面说的改一下
似乎可行？
4k+1的证明是不对
【在 d******k 的大作中提到】
: 第二点不对，感觉假设有限然后构造素数的简单方法无法证明这个命题
:
: 2*
|
|
|
m**x
发帖数: 8454 | 41 我整个方法都不对。看来不能把4k+1和4k+3单独讨论啊。
【在 n*****b 的大作中提到】
: 参考我上面说的改一下
: 似乎可行？
: 4k+1的证明是不对
|
n*****b
发帖数: 2235 | 42 不过我对你的反例的意见还是关于47
你假设的系统里没有这个数字
所以你无法用这个反例证明4k+1整除了235
【在 c**n 的大作中提到】
:
: 这种情况他用的是3*7*7+4
|
n*****b
发帖数: 2235 | 43 4k+3我觉得是对的阿
【在 m**x 的大作中提到】
: 我整个方法都不对。看来不能把4k+1和4k+3单独讨论啊。
|
m**x
发帖数: 8454 | 44 4k+3可以分解成4k+1和4k+3的积
【在 n*****b 的大作中提到】
: 你是对的
: 他原文说得不准确
: 我自动把证明修正了一下
: 把(2)改成了 这个数无法分解成4k+1类型的素数之积
|
n*****b
发帖数: 2235 | 45 对 但那些4k+3总要从p_1,..., p_k里取
这样就和(3)矛盾了
【在 m**x 的大作中提到】
: 4k+3可以分解成4k+1和4k+3的积
|
d******k
发帖数: 4295 | 46 这个也不对，我还是觉得这个命题高中数学解决不了。
【在 n*****b 的大作中提到】
: 参考我上面说的改一下
: 似乎可行？
: 4k+1的证明是不对
|
c**n
发帖数: 5275 | 47
你得证明一下这点，我试了10个没找着反例。。。太大了
【在 n*****b 的大作中提到】
: 你是对的
: 他原文说得不准确
: 我自动把证明修正了一下
: 把(2)改成了 这个数无法分解成4k+1类型的素数之积
|
m**x
发帖数: 8454 | 48 因为无论多少个4k+1乘起来最后的数肯定也是4k+1
【在 c**n 的大作中提到】
:
: 你得证明一下这点，我试了10个没找着反例。。。太大了
|
m**x
发帖数: 8454 | 49 原来如此，貌似可以照你说的那样改。
【在 n*****b 的大作中提到】
: 对 但那些4k+3总要从p_1,..., p_k里取
: 这样就和(3)矛盾了
|
c**n
发帖数: 5275 | 50
make sense了
【在 m**x 的大作中提到】
: 因为无论多少个4k+1乘起来最后的数肯定也是4k+1
|
|
|
n*****b
发帖数: 2235 | 51 我？我还是觉得这个证明是对的…
除了原文语言上的瑕疵
反例应该是不好找 :)
【在 c**n 的大作中提到】
:
: make sense了
|
n*****b
发帖数: 2235 | 52 原来他问的是这个
我没看明白问题
【在 m**x 的大作中提到】
: 因为无论多少个4k+1乘起来最后的数肯定也是4k+1
|
n*****n
发帖数: 1029 | 53 假设有限个素数，为p1
考虑：N = P2*P3...Pk，注意是从P2开始乘的，即3*5*7开始，没有2。
则N+2以及N+4均为素数（易证，略），且分别为4k+1和4k+3型的。
【在 x*****p 的大作中提到】
: 大家做个题吧。素数除了2以外全是奇素数，那就可分成两种类型。一种是4k+1型的，
: 如5, 13, 17, 29；一种是4k+3型的，如3, 7, 11, 19。请证明这两种类型的素数都有
: 无穷多个。
|
d******k
发帖数: 4295 | 54 恩，这样倒是对头。
上班灌水脑子不好用呀。
【在 n*****b 的大作中提到】
: 对 但那些4k+3总要从p_1,..., p_k里取
: 这样就和(3)矛盾了
|
n*****n
发帖数: 1029 | 55 刚贴出来，就发现一个逻辑问题，还得再想。呵呵
【在 n*****n 的大作中提到】
: 假设有限个素数，为p1: 考虑：N = P2*P3...Pk，注意是从P2开始乘的，即3*5*7开始，没有2。
: 则N+2以及N+4均为素数（易证，略），且分别为4k+1和4k+3型的。
|
d******k
发帖数: 4295 | 56 你和我犯得错误一样，呵呵
【在 n*****n 的大作中提到】
: 刚贴出来，就发现一个逻辑问题，还得再想。呵呵
|
c****n
发帖数: 1646 | 57 你这就是６３的证法，加上他那个实际用不上的素数定义以后。
【在 n*****n 的大作中提到】
: 假设有限个素数，为p1: 考虑：N = P2*P3...Pk，注意是从P2开始乘的，即3*5*7开始，没有2。
: 则N+2以及N+4均为素数（易证，略），且分别为4k+1和4k+3型的。
|
n*****n
发帖数: 1029 | 58 反证法，加构造法，加归谬法，呵呵。大的思路肯定是这样的，关键是构造那一步。
【在 c****n 的大作中提到】
: 你这就是６３的证法，加上他那个实际用不上的素数定义以后。
|
n*****n
发帖数: 1029 | 59 对，关键是可能是一个有限，而另一个无限，这就有点麻烦了。
【在 d******k 的大作中提到】
: 你和我犯得错误一样，呵呵
|
c****n
发帖数: 1646 | 60 你们的构造没什么一样，
我帮你把他那个素数的定义加上
a是素数 <=> a是大于1的自然数, 且a不被任何小于a的素数整除
假设有限个素数，为p1
考虑：N = P2*P3...Pk，注意是从P2开始乘的，即3*5*7开始，没有2。
则N+2以及N+4均为素数（易证，略），且分别为4k+1和4k+3型的。
他那么坚信他的方法没错，所以你也不要太担心。
【在 n*****n 的大作中提到】
: 反证法，加构造法，加归谬法，呵呵。大的思路肯定是这样的，关键是构造那一步。
|
|
|
I*********t
发帖数: 5258 | |
n*****n
发帖数: 1029 | 62 我估计你肯定没理解我在59里的说的是什么意思吧：“关键是可能是一个
有限，而另一个无限，这就有点麻烦了”。这才是我那个证法的主要
问题。现在还没到素数的定义那一步呢。呵呵。
【在 c****n 的大作中提到】
: 你们的构造没什么一样，
: 我帮你把他那个素数的定义加上
: a是素数 <=> a是大于1的自然数, 且a不被任何小于a的素数整除
: 假设有限个素数，为p1: 考虑：N = P2*P3...Pk，注意是从P2开始乘的，即3*5*7开始，没有2。
: 则N+2以及N+4均为素数（易证，略），且分别为4k+1和4k+3型的。
: 他那么坚信他的方法没错，所以你也不要太担心。
|
c****n
发帖数: 1646 | 63 不好意思，如果我看错了。
６３为了证明他的证明正确搞了一千多层的楼，
你如果认为他是对的，那你的证法也就没错。
【在 n*****n 的大作中提到】
: 我估计你肯定没理解我在59里的说的是什么意思吧：“关键是可能是一个
: 有限，而另一个无限，这就有点麻烦了”。这才是我那个证法的主要
: 问题。现在还没到素数的定义那一步呢。呵呵。
|
m**x
发帖数: 8454 | |
n*****b
发帖数: 2235 | |
n*****n
发帖数: 1029 | 66 如果你觉得我的证法和I63的证法仅仅是构造上的不同，那你应该是看错了。
还是那句话，你得先理解了59楼里的东西才行。谢谢！
【在 c****n 的大作中提到】
: 不好意思，如果我看错了。
: ６３为了证明他的证明正确搞了一千多层的楼，
: 你如果认为他是对的，那你的证法也就没错。
|
c**n
发帖数: 5275 | |
n**u
发帖数: 6997 | |
c****n
发帖数: 1646 | 69 我想我明白你的意思，有一类素数可能无限，不能用那个素数有限的假设。
不过我们跳一步说，
这是一个证明素数无限的反证法，你觉得对否？
【在 n*****n 的大作中提到】
: 如果你觉得我的证法和I63的证法仅仅是构造上的不同，那你应该是看错了。
: 还是那句话，你得先理解了59楼里的东西才行。谢谢！
|
n*****n
发帖数: 1029 | 70 “我想我明白你的意思，有一类素数可能无限，不能用那个素数有限的假设”，就这
一句就知道你还没明白。呵呵。
【在 c****n 的大作中提到】
: 我想我明白你的意思，有一类素数可能无限，不能用那个素数有限的假设。
: 不过我们跳一步说，
: 这是一个证明素数无限的反证法，你觉得对否？
|
|
|
d******k
发帖数: 4295 | |
n*****b
发帖数: 2235 | 72 您看懂第二个证明的关键那步了吗
这个证明跟板上大伙的思路一样
就是(-1/p)=1那句承上启下是关键
但我老都不知道(..)在这句话里面是什么定义
惭愧
【在 d******k 的大作中提到】
: 费曼小定理呀，好久没见了。
|
l*****9
发帖数: 9501 | |
l*3
发帖数: 2279 | 74 楼主既然声称 "只需要以前的反证法即可"
还求你来一个 "以前的反证法" 那样的证明, 谢谢!
让我等白痴学习一下.
【在 x*****p 的大作中提到】
: 对于4k+3的类型，不需要高深的法子，只需要以前的反证法即可。但构造的时候有点技
: 巧罢了。
|
S*E
发帖数: 3662 | 75 N*N 1不含有4k 3型素数。
4K 1素数无穷怎么证啊想不出来。
【在 m**x 的大作中提到】
: 4K+1素数无穷怎么证啊
: 想不出来。
|
S*E
发帖数: 3662 | 76 对任何整数N，N*N 1不含有4K 3型素数因子。
N*N 1不含有4k 3型素数。
【在 S*E 的大作中提到】
: N*N 1不含有4k 3型素数。
:
: 4K 1素数无穷怎么证啊想不出来。
|
d******k
发帖数: 4295 | 77 http://en.wikipedia.org/wiki/Quadratic_residue
http://en.wikipedia.org/wiki/Law_of_quadratic_reciprocity
【在 n*****b 的大作中提到】
: 您看懂第二个证明的关键那步了吗
: 这个证明跟板上大伙的思路一样
: 就是(-1/p)=1那句承上启下是关键
: 但我老都不知道(..)在这句话里面是什么定义
: 惭愧
|
x*****p
发帖数: 1707 | 78 我们假设有有限个4k+3类型的素数为p_1, p_2, ..., p_k。
有一个性质我们要用上。4k+1型的数的乘积必然是4k+1型的数。偶数个4k+3型的数的乘
积是4k+1型的数，而奇数个4k+3型的数的乘积还是4k+3型的数。
分两种情况考虑。
(1) k为偶数，p_1*p_2*...*p_k为4k+1型的数，我设 N = p_1*p_2*...*p_k + 2. 那么
N为4k+3型的数。如果N是素数，我们找到一个新的4k+3型的素数，推出矛盾。如果N不
是素数，那研究N的所有素因子。因为任何4k+3刑的素数不能整除N，那么所有N的素因
子必4k+1是型的素数。但我们发现，任何多个4k+1型的素数乘积必然是一个4k+1型的数
，可N是4k+3型的数，我们也得到矛盾。
(2) k为奇数，p_1*p_2*...*p_k为4k+3型的数, 我设 N = p_1*p_2*...*p_k + 4，那么
N为4k+3型的数。同(1)一样，我们可以得到矛盾。
所以4k+3型的素数为无穷多个。
【在 l*3 的大作中提到】
: 楼主既然声称 "只需要以前的反证法即可"
: 还求你来一个 "以前的反证法" 那样的证明, 谢谢!
: 让我等白痴学习一下.
|
m**x
发帖数: 8454 | 79 it's virtually the same as the proof I gave in the update of floor#20. and
you didn't give the proof for infinity number of 4k+1 primes
【在 x*****p 的大作中提到】
: 我们假设有有限个4k+3类型的素数为p_1, p_2, ..., p_k。
: 有一个性质我们要用上。4k+1型的数的乘积必然是4k+1型的数。偶数个4k+3型的数的乘
: 积是4k+1型的数，而奇数个4k+3型的数的乘积还是4k+3型的数。
: 分两种情况考虑。
: (1) k为偶数，p_1*p_2*...*p_k为4k+1型的数，我设 N = p_1*p_2*...*p_k + 2. 那么
: N为4k+3型的数。如果N是素数，我们找到一个新的4k+3型的素数，推出矛盾。如果N不
: 是素数，那研究N的所有素因子。因为任何4k+3刑的素数不能整除N，那么所有N的素因
: 子必4k+1是型的素数。但我们发现，任何多个4k+1型的素数乘积必然是一个4k+1型的数
: ，可N是4k+3型的数，我们也得到矛盾。
: (2) k为奇数，p_1*p_2*...*p_k为4k+3型的数, 我设 N = p_1*p_2*...*p_k + 4，那么
|
C**********r
发帖数: 8189 | 80 同学，上次华人那幢楼又有更新了。不过不精彩了。
【在 c**n 的大作中提到】
:
: 不错有意思
|
|
|
C**********r
发帖数: 8189 | 81 Good one!
many
【在 b***y 的大作中提到】
: Easy.
: By Yitang Zhang's Theorem, (to be completed soon), there are infinitely many
: pairs of prime numbers that differ by 2. Therefore, there are infinitely
: many prime numbers taking both the forms of 4k+1 and 4k+3.
: End of proof.
|
x*****p
发帖数: 1707 | 82 只是应I63的要求一证，没细看每一楼的贴子。
【在 m**x 的大作中提到】
: it's virtually the same as the proof I gave in the update of floor#20. and
: you didn't give the proof for infinity number of 4k+1 primes
|
m**x
发帖数: 8454 | 83 这个用初等数学如何证明呢？
【在 S*E 的大作中提到】
: 对任何整数N，N*N 1不含有4K 3型素数因子。
:
: N*N 1不含有4k 3型素数。
|
x*****p
发帖数: 1707 | 84 N*N 1是什么意思？是N*N+1吗？
【在 m**x 的大作中提到】
: 这个用初等数学如何证明呢？
|
m**x
发帖数: 8454 | 85 i guess so
【在 x*****p 的大作中提到】
: N*N 1是什么意思？是N*N+1吗？
|
d******k
发帖数: 4295 | 86 这个涉及到数论里的二次互反律， 不是初等数学能搞定的了。
高斯给过一个相对初等的证明，
http://en.wikipedia.org/wiki/Gauss%27s_lemma_%28number_theory%2
【在 m**x 的大作中提到】
: 这个用初等数学如何证明呢？
|
O********2
发帖数: 121 | 87 N*N+1 does not contain prime factor of the form 4k+3.
Proof: Let M = N*N + 1 and assume that M contains a prime factor p of the
form 4k+3. Then we have the following two observations.
(1) gcd(p,N) = 1. According to Fermat's little theorem,
N^(p-1) = 1 (mod p)
(2) p|M = N*N + 1, then N*N = N^2 = -1 (mod p), then N^4 = 1 (mod p)
Now both N^(p-1) and N^2 are equal to 1 (mod p), let k = gcd(4, p-1) and we
have N^k = 1 (mod p)
Since p has form 4k+3, the p-1 = 4k+2 and thus k = gcd(4, 4k+2) = 2, then we
get N^2 = 1 (mod p). But N^2 = -1 (mod p) and thus 1 = -1 (mod p). Then we
get p = 2 which is not in the form of 4k+3. We get a contradiction.
Done. |
O********2
发帖数: 121 | 88 有了楼上的结果，我们可以证明4k+1型的素数有无穷多个了。
假设只有有限个4k+1型的素数p_1, ..., p_k，我们考虑 N = 2*p_1*p_2*...*p_k，再
假设 M = N^2 + 1. 我们发现M是个4k+1型的数，且不能被任何一个4k+1型的素数p_i整
除。那么如果M是素数，我们就找到一个新的4k+1型的素数，推出矛盾。如果M不是素数
，根据87楼的结论，所有M的素因子都是4k+1型的素数，所以M必有一个新的素因子是4k
+1型的，依然推出矛盾。 |
m**x
发帖数: 8454 | 89 sorry, what is N?
we
we
we
【在 O********2 的大作中提到】
: N*N+1 does not contain prime factor of the form 4k+3.
: Proof: Let M = N*N + 1 and assume that M contains a prime factor p of the
: form 4k+3. Then we have the following two observations.
: (1) gcd(p,N) = 1. According to Fermat's little theorem,
: N^(p-1) = 1 (mod p)
: (2) p|M = N*N + 1, then N*N = N^2 = -1 (mod p), then N^4 = 1 (mod p)
: Now both N^(p-1) and N^2 are equal to 1 (mod p), let k = gcd(4, p-1) and we
: have N^k = 1 (mod p)
: Since p has form 4k+3, the p-1 = 4k+2 and thus k = gcd(4, 4k+2) = 2, then we
: get N^2 = 1 (mod p). But N^2 = -1 (mod p) and thus 1 = -1 (mod p). Then we
|
O********2
发帖数: 121 | 90 N is any positive integer greater than 1.
【在 m**x 的大作中提到】
: sorry, what is N?
:
: we
: we
: we
|
|
|
m**x
发帖数: 8454 | 91 then why gcd(p,N) = 1?
【在 O********2 的大作中提到】
: N is any positive integer greater than 1.
|
O********2
发帖数: 121 | 92 p is a prime, p divides M = N*N + 1, then p does not divide N. So gcd(p,N)=1
.
【在 m**x 的大作中提到】
: then why gcd(p,N) = 1?
|
m**x
发帖数: 8454 | 93 I must have forgotten all the modulus stuff...
one last question, how do you get:
both N^(p-1) and N^2 are equal to 1 (mod p), let k = gcd(4, p-1) and we
have N^k = 1 (mod p)
=1
【在 O********2 的大作中提到】
: p is a prime, p divides M = N*N + 1, then p does not divide N. So gcd(p,N)=1
: .
|
O********2
发帖数: 121 | 94 We know, if k = gcd(a,b), then we can find some integers x and y, such that
ax + by = k.
Since k = gcd(4, p-1), then we can find x and y, such that
4x + (p-1)y = k
Then N^k = N^(4x + (p-1)y) = (N^4)^x * (N^(p-1))^y = 1^x * 1^y = 1 (mod p)
【在 m**x 的大作中提到】
: I must have forgotten all the modulus stuff...
: one last question, how do you get:
: both N^(p-1) and N^2 are equal to 1 (mod p), let k = gcd(4, p-1) and we
: have N^k = 1 (mod p)
:
: =1
|
m**x
发帖数: 8454 | 95 thx. admire
that
【在 O********2 的大作中提到】
: We know, if k = gcd(a,b), then we can find some integers x and y, such that
: ax + by = k.
: Since k = gcd(4, p-1), then we can find x and y, such that
: 4x + (p-1)y = k
: Then N^k = N^(4x + (p-1)y) = (N^4)^x * (N^(p-1))^y = 1^x * 1^y = 1 (mod p)
|
m**x
发帖数: 8454 | 96 看到Legendre symbol我就头晕, 这个东东和小括号长得有半点区别么？
【在 d******k 的大作中提到】
: 这个涉及到数论里的二次互反律， 不是初等数学能搞定的了。
: 高斯给过一个相对初等的证明，
: http://en.wikipedia.org/wiki/Gauss%27s_lemma_%28number_theory%2
|
H******9
发帖数: 8087 | 97 太高深了，就是不明白，就算有无穷多个，对我们有用吗
【在 x*****p 的大作中提到】
: 大家做个题吧。素数除了2以外全是奇素数，那就可分成两种类型。一种是4k+1型的，
: 如5, 13, 17, 29；一种是4k+3型的，如3, 7, 11, 19。请证明这两种类型的素数都有
: 无穷多个。
|
m**x
发帖数: 8454 | 98 别问有用没用。书到用时方恨少，数学定理也是一样。
【在 H******9 的大作中提到】
: 太高深了，就是不明白，就算有无穷多个，对我们有用吗
|
d******k
发帖数: 4295 | 99 写法没啥区别吧，起码latex敲公式都是一样。
【在 m**x 的大作中提到】
: 看到Legendre symbol我就头晕, 这个东东和小括号长得有半点区别么？
|
n*****b
发帖数: 2235 | 100 我不是头晕
我是脑子一片空白 完全想不起来它了 :)
【在 m**x 的大作中提到】
: 看到Legendre symbol我就头晕, 这个东东和小括号长得有半点区别么？
|
|
|
m**x
发帖数: 8454 | 101 我不是想不起来它， 我是根本就不知道它是啥。
【在 n*****b 的大作中提到】
: 我不是头晕
: 我是脑子一片空白 完全想不起来它了 :)
|
n*****b
发帖数: 2235 | 102 Thanks a lot.
we
we
we
【在 O********2 的大作中提到】
: N*N+1 does not contain prime factor of the form 4k+3.
: Proof: Let M = N*N + 1 and assume that M contains a prime factor p of the
: form 4k+3. Then we have the following two observations.
: (1) gcd(p,N) = 1. According to Fermat's little theorem,
: N^(p-1) = 1 (mod p)
: (2) p|M = N*N + 1, then N*N = N^2 = -1 (mod p), then N^4 = 1 (mod p)
: Now both N^(p-1) and N^2 are equal to 1 (mod p), let k = gcd(4, p-1) and we
: have N^k = 1 (mod p)
: Since p has form 4k+3, the p-1 = 4k+2 and thus k = gcd(4, 4k+2) = 2, then we
: get N^2 = 1 (mod p). But N^2 = -1 (mod p) and thus 1 = -1 (mod p). Then we
|
n*****b
发帖数: 2235 | 103 希望水版有更多这样的坑
数学版排名骂架很忙
让水版成为我们的学术类数学版吧
【在 m**x 的大作中提到】
: 我不是想不起来它， 我是根本就不知道它是啥。
|
x*****p
发帖数: 1707 | 104 在初等数论中，一个重要的问题是判断一个数a是另一个数p的二次剩余或者二次非剩余
，而Legendre symbol和Jacobi symbol就是用来作判断的。
对于Legendre symbol (a/p), 如果a是p的二次剩余，则(a/p)=1；如果a是p的二次非剩
余，则(a/p)=-1。
对于奇素数p来说，它的有限域Zp有p-1个(偶数个)非零的数。其中恰好有一半是p的二
次剩余，而另一半是p的二次非剩余。用这个性质，就可以对一个非常大的奇数做素性
判断。而Legendre symbol用二次互反律可以在多项式时间内完成计算，于是可以借助
计算机来找
非常大的素数。RSA公钥体系中的大数就是如此产生的。
【在 m**x 的大作中提到】
: 我不是想不起来它， 我是根本就不知道它是啥。
|
n*****b
发帖数: 2235 | 105 上代数的时候还学过这个 真惭愧全忘了
【在 x*****p 的大作中提到】
: 在初等数论中，一个重要的问题是判断一个数a是另一个数p的二次剩余或者二次非剩余
: ，而Legendre symbol和Jacobi symbol就是用来作判断的。
: 对于Legendre symbol (a/p), 如果a是p的二次剩余，则(a/p)=1；如果a是p的二次非剩
: 余，则(a/p)=-1。
: 对于奇素数p来说，它的有限域Zp有p-1个(偶数个)非零的数。其中恰好有一半是p的二
: 次剩余，而另一半是p的二次非剩余。用这个性质，就可以对一个非常大的奇数做素性
: 判断。而Legendre symbol用二次互反律可以在多项式时间内完成计算，于是可以借助
: 计算机来找
: 非常大的素数。RSA公钥体系中的大数就是如此产生的。
|
m**x
发帖数: 8454 | 106 google了一下，貌似这些是初等数论里的概念。初等数论只有数学专业的才学吧？
【在 x*****p 的大作中提到】
: 在初等数论中，一个重要的问题是判断一个数a是另一个数p的二次剩余或者二次非剩余
: ，而Legendre symbol和Jacobi symbol就是用来作判断的。
: 对于Legendre symbol (a/p), 如果a是p的二次剩余，则(a/p)=1；如果a是p的二次非剩
: 余，则(a/p)=-1。
: 对于奇素数p来说，它的有限域Zp有p-1个(偶数个)非零的数。其中恰好有一半是p的二
: 次剩余，而另一半是p的二次非剩余。用这个性质，就可以对一个非常大的奇数做素性
: 判断。而Legendre symbol用二次互反律可以在多项式时间内完成计算，于是可以借助
: 计算机来找
: 非常大的素数。RSA公钥体系中的大数就是如此产生的。
|
l*****8
发帖数: 16949 | 107 其实这个算法找出来的不一定是素数，只不过不是素数的概率极小。
【在 x*****p 的大作中提到】
: 在初等数论中，一个重要的问题是判断一个数a是另一个数p的二次剩余或者二次非剩余
: ，而Legendre symbol和Jacobi symbol就是用来作判断的。
: 对于Legendre symbol (a/p), 如果a是p的二次剩余，则(a/p)=1；如果a是p的二次非剩
: 余，则(a/p)=-1。
: 对于奇素数p来说，它的有限域Zp有p-1个(偶数个)非零的数。其中恰好有一半是p的二
: 次剩余，而另一半是p的二次非剩余。用这个性质，就可以对一个非常大的奇数做素性
: 判断。而Legendre symbol用二次互反律可以在多项式时间内完成计算，于是可以借助
: 计算机来找
: 非常大的素数。RSA公钥体系中的大数就是如此产生的。
|
x*****p
发帖数: 1707 | 108 测100个数，算二次剩余。不是素数的概率只有1/2^100。
【在 l*****8 的大作中提到】
: 其实这个算法找出来的不一定是素数，只不过不是素数的概率极小。
|
l*3
发帖数: 2279 | 109 是对的, 厉害.
【在 x*****p 的大作中提到】
: 我们假设有有限个4k+3类型的素数为p_1, p_2, ..., p_k。
: 有一个性质我们要用上。4k+1型的数的乘积必然是4k+1型的数。偶数个4k+3型的数的乘
: 积是4k+1型的数，而奇数个4k+3型的数的乘积还是4k+3型的数。
: 分两种情况考虑。
: (1) k为偶数，p_1*p_2*...*p_k为4k+1型的数，我设 N = p_1*p_2*...*p_k + 2. 那么
: N为4k+3型的数。如果N是素数，我们找到一个新的4k+3型的素数，推出矛盾。如果N不
: 是素数，那研究N的所有素因子。因为任何4k+3刑的素数不能整除N，那么所有N的素因
: 子必4k+1是型的素数。但我们发现，任何多个4k+1型的素数乘积必然是一个4k+1型的数
: ，可N是4k+3型的数，我们也得到矛盾。
: (2) k为奇数，p_1*p_2*...*p_k为4k+3型的数, 我设 N = p_1*p_2*...*p_k + 4，那么
|
m********3
发帖数: 2125 | 110 下面的反证法是从书上通俗翻译过来的：
假设只有有限个4k-1类型的素数p1,p2,...pk
那么考虑N=4*p1*p2*..Pk-1这个数。
这个数的质因数不能是任何一个4k-1类型的素数（因为除了后还余1）；
那么它的质因数只能是4K+1类型的（当然大家都知道更不可能是4K或者是4K+2类型的了）
N=(4k1+1)(4k2+1)(4k3+1)...(4kn+1)
把括号里面的分解出来会发现N是4×（。。。。。）+1
矛盾出来了：
刚才N明明是4×(p1*p2*p3..)-1,这里又成了4X(....)+1,不可能的。
类似的证明用于4k+1就行不通了，因为（4k1-1）（4k2-1)(4k3-1)....(4kn-1)分解出
来有时是4K+1，有时是4K-1.
【在 x*****p 的大作中提到】
: 大家做个题吧。素数除了2以外全是奇素数，那就可分成两种类型。一种是4k+1型的，
: 如5, 13, 17, 29；一种是4k+3型的，如3, 7, 11, 19。请证明这两种类型的素数都有
: 无穷多个。
|
|
|
C**********r
发帖数: 8189 | 111 这个说的很简单明了。求书名。
了）
【在 m********3 的大作中提到】
: 下面的反证法是从书上通俗翻译过来的：
: 假设只有有限个4k-1类型的素数p1,p2,...pk
: 那么考虑N=4*p1*p2*..Pk-1这个数。
: 这个数的质因数不能是任何一个4k-1类型的素数（因为除了后还余1）；
: 那么它的质因数只能是4K+1类型的（当然大家都知道更不可能是4K或者是4K+2类型的了）
: N=(4k1+1)(4k2+1)(4k3+1)...(4kn+1)
: 把括号里面的分解出来会发现N是4×（。。。。。）+1
: 矛盾出来了：
: 刚才N明明是4×(p1*p2*p3..)-1,这里又成了4X(....)+1,不可能的。
: 类似的证明用于4k+1就行不通了，因为（4k1-1）（4k2-1)(4k3-1)....(4kn-1)分解出
|
