【趣题征解】求所有的素数 p,q（p≤q），使得 (5^p-2^p)(5^q-2^q) 能被 pq 整除

luyuanhong

【趣题征解】求所有的素数 p,q（p≤q），使得 (5^p-2^p)(5^q-2^q) 能被 pq 整除。

w632158

luyuanhong

楼上 w632158 的解法不完整，除了 p=q=3 以外，本题还有一个解：p=3 ，q=13 。

w632158

p=3时，前面的因数是67是素数，不含13

luyuanhong

下面引用由w632158在 2011/08/23 10:34am 发表的内容：
-=-=-=-=- 以下内容由w632158在时添加 -=-=-=-=-
p=3时，前面的因数是67是素数，不含13

p＝3 ，q＝13 时，
（5^p-2^p)(5^q-2^q)＝(5^3-2^3)(5^q-2^q)＝117×(5^q-2^q)＝3^2×13×(5^q-2^q)
可以被 pq＝3×13 整除。

w632158

我算错了，把5的3次算成75了，呵呵！

luyuanhong

[这个贴子最后由luyuanhong在 2011/08/28 06:36am 第 1 次编辑]

【趣题征解】求所有的素数 p,q（p≤q），使得 (5^p-2^p)(5^q-2^q) 能被 pq 整除。

【解】因为 5^p 是奇数，2^p 是偶数，所以 5^p-2^p 是奇数。同理，5^q-2^q 也是奇数，
所以 (5^p-2^p)(5^q-2^q) 是奇数，所以 p≠2 ，q≠2 。
    因为 p 是素数，所以由 Fermat 小定理可知，必有
    5^p≡5（mod p) ，2^p≡2（mod p) ，5^p-2^p≡5-2≡3（mod p) 。
    假设 p＞3 ，由上式可看出：这时 p 不是 5^p-2^p 的因子，因此 p 必须是 5^q-2^q
的因子，必有 5^q-2^q≡0(mod p) ，即有 5^q≡2^q(mod p) 。
    另外，由 Fermat 小定理可知，必有 5^(p-1)≡1≡2^(p-1)(mod p) 。
    因为 q≥p＞p-1 ，q 与 p-1 互素，所以指数 q 与 p-1 可辗转相减最后得到１，这样
就会有 5≡5^1≡2^1≡2(mod p) ，显然这是不可能的，所以假设不成立，不可能有 p＞3 ，
只可能是 p＝3 。
    当 q＝p＝3 时，(5^p-2^p)(5^q-2^q)＝(5^３-2^3)×(5^３-2^3)＝117^2＝3^4×13^2
确实能够被 pq＝3^2 整除。
    当 q＞p＝3 时，由 5^q-2^q≡5-2≡3（mod q) 可看出：这时 q 不是 5^q-2^q 的因子，
q 必须是 5^p-2^p＝5^３-2^３＝117＝3^2×13 的因子。由于 q＞3 ，所以只能是 q＝13 。
    当 p＝3，q＝13 时，(5^p-2^p)(5^q-2^q)＝(5^３-2^3)(5^13-2^13)＝117×(5^13-2^13)
＝3^2×13×(5^13-2^13) 确实能够被 pq＝3×13 整除。
    所以，本题有两组解：q＝p＝3 和 p＝3，q＝13 。