CpawCTF Q26.[PPC]Remainder theorem

CpawCTF - Main page

x ≡ 32134 (mod 1584891)
x ≡ 193127 (mod 3438478)

x = ?

フラグはcpaw{xの値}です！

問題文から「1584891で割って余り32134」かつ「3438478で割って193127余り」の数字を探せばいいことがわかる（modはその数字で割った余りを表す）。効率的かはわからないが、Pythonでプログラムするとこんな感じ。

for i in range(0, 1000000):
   k = i * 3438478 + 193127 # 3438478で割って193127余る
   if k % 1584891 == 32134: # 1584891で割って32134余る
       print(k)
       break

CpawCTF write-upまとめへ