素数题目一枚

昨天偶然看到一个题目：求所有的素数对(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的倍数

[color=Silver][[i] 本帖最后由 青石 于 2009-4-15 11:49 编辑 [/i]][/color]

求所有的素数对(p,q)使得5^p+5^q是pq的倍数

显然（5，2） （2，5），（5，5）满足条件

p=q 只有一组解（5，5）

如何解呢？可以的话仅用初等数学

此类算法先确认大致范围
因为有
n^m<=nm
所以数值范围不会太大
而后用穷举法破解

以上是挖的思路

或许用小程序计算更快

n^m<=nm

这个有范围的:titter:  不是对任意的都正确

如果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)
这些根本不能算是初等数学内容吧，不过是初等数论- -

[quote]原帖由 [i]wotaifu[/i] 于 2009-4-17 12:19 发表
用费马小定理有5^pq-5能被pq整除[/quote]

这个有问题。

比如取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的倍数


费尔马小定理要求指数是素数。

噢，如此看来你的解答后面一部分是有问题的。

[color=Silver][[i] 本帖最后由 青石 于 2009-4-18 12:01 编辑 [/i]][/color]

汗忘记定理成立条件了。全都大于5的数组的情况暂时还没头绪，不过倾向于认为没有

大概2的情况比较特殊

奇素数的情况解法估计是一样的