今週の問題　問44　答え

上野竜生です。問44の答えを発表します。

問44　★

答え

2019=3×673であり673は素数である。
3で割った余りと673で割った余りにわけて考える。
<条件3>を満たすことを考える。よってn³を3,673で割った余りはどちらも1。
3で割った余りに着目すると
nを3で割った余りが0のときn³を3で割った余りは0
nを3で割った余りが1のときn³を3で割った余りは1
nを3で割った余りが2のときn³を3で割った余りは2
なのでnを3で割った余りは1になる。
よって次の命題を考えればよい。（次の命題が成り立てば問題の答えは「存在しない」であり，命題が成り立たなければ問題の答えは「存在する」である。）

命題「n³を673で割った余りが1ならばnを673で割った余りは1」

フェルマーの小定理より2⁶⁷²を673で割った余りは1
ここで2²²⁴を673で割った余りを調べてみる。以下すべて(mod 673)
2¹≡2, 2²≡4 , 2⁴≡16 , 2⁸≡256 , 2¹⁶≡65536≡255 , 2³²=65025≡417 , 2⁶⁴≡173889≡255
2¹²⁸≡417より　2²²⁴=2¹²⁸・2⁶⁴・2³²≡417・255・417≡44341695≡417
よってnを673で割った余りが417ならばn³を673で割った余りは1

∴命題は成り立たない。

（2⁴⁴⁸≡417²≡173889≡255よりnを673で割った余りが255のときもn³を673で割った余りは1）
よってnを3で割った余りが1かつnを673で割った余りが255または417となる自然数，つまり
nを2019で割った余りが928,1090のとき<条件1><条件3>を満たす。
このときn²≡861184,1188100≡417 , 255なので<条件2>も満たす。
以上より3条件をすべて満たす自然数は存在する。（nを2019で割った余りが928または1090である自然数）

正解者　1名（kuheiya さま）