标题: 素数题目一枚 [打印本页]
作者:
青石 时间: 2009-4-15 11:47 标题: 素数题目一枚
昨天偶然看到一个题目：求所有的素数对(p,q)使得5^p+5^q是pq的倍数。
5换成其他素数也可以吧
比如
求所有的素数对(p,q)使得2^p+2^q是pq的倍数
求所有的素数对(p,q)使得3^p+3^q是pq的倍数
求所有的素数对(p,q)使得7^p+7^q是pq的倍数
求所有的素数对(p,q)使得11^p+11^q是pq的倍数
如果换成合数呢？比如
求所有的素数对(p,q)使得6^p+6^q是pq的倍数
如果是三个的话会怎么样？
求所有的素数对(p,q,r)使得5^p+5^q+5^r是pqr的倍数
[ 本帖最后由 青石 于 2009-4-15 11:49 编辑 ]
作者:
青石 时间: 2009-4-15 17:51
求所有的素数对(p,q)使得5^p+5^q是pq的倍数
显然（5，2） （2，5），（5，5）满足条件
p=q 只有一组解（5，5）
作者:
KYOKO 时间: 2009-4-15 23:23
如何解呢？可以的话仅用初等数学
作者:
司徒苍月 时间: 2009-4-16 12:26
此类算法先确认大致范围
因为有
n^m<=nm
所以数值范围不会太大
而后用穷举法破解
以上是挖的思路
或许用小程序计算更快
作者:
青石 时间: 2009-4-16 18:38
n^m<=nm
这个有范围的
不是对任意的都正确
作者:
wotaifu 时间: 2009-4-17 12:19
如果p=q,那么5^p+5^q=2*5^p.只有素因子2，5.显然p=q=2时不成立。因此(5,5)是一对。
如果p不等于q,不妨设p>q。5^p+5^q=[5^(p-q)+1]*5^q.如果q=2,那么p=5成立。如果p不等于5，则5^p-5能被p整除（费马小定理）。因此5^p+5^2=5^p-5+30.要求p能整除30.于是p=3.(5,2)(3,2)都成立。
显然(5,3)不成立。如果q=5,则5^p+5^q=5^p-5+3130.p要被3130整除，又p>q,于是只能p=313.(313,5)成立。
当q>5时，首先p,q都是奇数。然后用费马小定理有5^pq-5能被pq整除。但是5^p+5^q=5^p-5+5+5^q能被p整除，因此5^pq+5^p是5^q+5的倍数也能被p整除。然后得到5^pq+5能被p整除。同理可证5^pq+5能被q整除。于是10=(5^pq+5)-(5^pq-5)是pq的倍数，矛盾。
所以一共可行的数组有(5,5)(5,2)(2,5)(3,2)(2,3)(313,5)(5,313)
这些根本不能算是初等数学内容吧，不过是初等数论- -
作者:
青石 时间: 2009-4-18 11:55
原帖由 wotaifu 于 2009-4-17 12:19 发表
用费马小定理有5^pq-5能被pq整除
这个有问题。
比如取p=3 q=2 但是5^6-5=5x(5^5-1)=5x3124=2x2x5x11x71不是6的倍数
取p=11 q=7 但是5^77-5=5x(5^76-1)也不是77的倍数
费尔马小定理要求指数是素数。
噢，如此看来你的解答后面一部分是有问题的。
[ 本帖最后由 青石 于 2009-4-18 12:01 编辑 ]
作者:
wotaifu 时间: 2009-4-22 20:44
汗忘记定理成立条件了。全都大于5的数组的情况暂时还没头绪，不过倾向于认为没有
作者:
青石 时间: 2009-5-8 01:17
大概2的情况比较特殊
奇素数的情况解法估计是一样的
| 欢迎光临 轩辕春秋文化论坛 (http://xycq.org.cn/forum/) |
Powered by Discuz! 5.0.0 |