看板 Math 關於我們 聯絡資訊
prove or disprove there exists 2 primes p and q such that (p-1)^q≡100 (mod pq) 沒什麼頭緒從哪邊下手 想請問該怎麼出發 -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 111.253.6.150 (臺灣) ※ 文章網址: https://www.ptt.cc/bbs/Math/M.1576217924.A.968.html
chemmachine : both p=11 and q=2 are as desired. 12/13 16:48
GaussQQ : 中國剩餘定理 和 (p-1)^q -100=0 mod p 12/13 17:21
GaussQQ : 不用中國... 12/13 17:25
DLHZ : 不太了解 後面的式子有名字或過程嗎? 12/13 21:19
Ifault : (p-1)^q=pqx+100 pq>100 12/13 22:26
Ifault : 左邊就二次項定理 若q=偶數=> p*([email protected]#$%)+1=100 12/13 22:27
Ifault : p有可能是 3or11 q=2 12/13 22:28
Ifault : q=奇數 p*([email protected]#$)-1=100 = 101 p=101 12/13 22:34
Ifault : 然後我不會了 12/13 22:38
kilva : 一樓給出例子了,100≡100 (mod 22) 12/13 23:09
GaussQQ : 後面的式子就同餘定義 12/13 23:11
GaussQQ : 因此 q>2 => p=101. 代回得到 100^q =100 mod q 這F 12/13 23:17
GaussQQ : ermat 小定理就一堆了 12/13 23:17
GaussQQ : 因此有一堆解 q=3,7,11都可以吧 12/13 23:18
DLHZ : 感謝你 12/14 10:25