作业帮 > 数学 > 作业

求几道质数证明题(1)一个质数p问有多少小于p的正整数和p互质(2)一个质数p是奇数问有多少小于2p的正整数和2p互质

来源:学生作业帮 编辑:灵鹊做题网作业帮 分类:数学作业 时间:2024/04/28 18:24:07
求几道质数证明题
(1)一个质数p
问有多少小于p的正整数和p互质
(2)一个质数p是奇数
问有多少小于2p的正整数和2p互质
求几道质数证明题(1)一个质数p问有多少小于p的正整数和p互质(2)一个质数p是奇数问有多少小于2p的正整数和2p互质
1) p-1个
互质(relatively primeì)又叫互素.若N个整数的最大公因数是1,则称这N个整数互质.因为p只有两个因数,一个是他本身一个是1;小于p的正整数有p-1个,这些数与p的最大公因子都是1
2)2p-2个
因为2p和p与p不互质,除去这两个数外,还有2p-2个数,与p的最大公因数是1