[數論] 同餘

[DLHZ (going faster)]

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.
推 GaussQQ     : 中國剩餘定理 和 （p-1)^q -100=0 mod p
推 GaussQQ     : 不用中國...
→ DLHZ        : 不太了解 後面的式子有名字或過程嗎?
推 Ifault      : (p-1)^q=pqx+100 pq>100
→ Ifault      : 左邊就二次項定理 若q=偶數=> p*(!@#$%)+1=100
→ Ifault      : p有可能是 3or11 q=2
→ Ifault      : q=奇數 p*(!@#$)-1=100 = 101  p=101
推 Ifault      : 然後我不會了
→ kilva       : 一樓給出例子了，100≡100 (mod 22)
推 GaussQQ     : 後面的式子就同餘定義
推 GaussQQ     : 因此 q>2 => p=101. 代回得到 100^q =100 mod q 這F
→ GaussQQ     : ermat 小定理就一堆了
→ GaussQQ     : 因此有一堆解 q=3,7,11都可以吧
→ DLHZ        : 感謝你