2017は3つの条件を満たす第1の素数です。第二は何ですか?

  1. $ 2017 $は素数で$(2017 + 1)/ 2 = 1009 $です。

  2. $ 2017 $は$ a ^ 2 + b ^ 4 $と書くことができます: $ 2017 = 44 ^ 2 + 3 ^ 4 =
    1936 + 81 $

  3. $ 2017 equiv 2 bmod 31 $。

これらの同じ3つの条件を満たす次の素数(もしあれば)は何ですか?

ベストアンサー

実際には、モジュラ演算と忍耐のビットを使用すると、コードなしのソリューションを見つけることができます。

見ている$ mod 3 $:

$ p $、$ p + 1 $は3で割り切れないことに注意してください。したがって、$ p equiv 1 mod 3
$。

見ている$ mod 4 $:

四角形と4乗は0または1 mod 4なので、その和は0,1または2 mod 4です。明らかに1 mod
4しか使用できないので、$ p equiv 1 mod 4 $です。

見ている$ mod 5 $:

正方形は、0,1または4 mod 5、4乗0または1 mod 5です。$ p $も$ p + 1
$も5で割り切れないことに注意してください。これは$ p equiv 1 mod 5 $または$ p equiv 2
mod 5 $。

見ている$ mod 31 $:

$ p equiv 2 mod 31 $が与えられます。

中国の剰余定理との結合:

$ 3 cdot 4 cdot 5 cdot 31 = 1860 $となるので、mod
1860を見る必要があります。$ 201 equiv 2 mod 5 $になるので、$ p equiv 2 mod 5
$は合同は$ p equiv 2017 equiv 157 mod 1860 $です。もう1つの可能性は、$ p
equiv 1 mod 60 $と$ p equiv 2 mod 31 $を与えます。これにより、$ p equiv
901 mod 1860 $が得られます。

さて、いくつかの可能性が残っています:

  • $ p = 157 $と$ p = 901 $は、$ 2017 $が最小であることが理由で破棄されます。
  • $ p = 2761 $は11で割り切れる(合計和検定)。
  • $ p = 3877 $は$(p + 1)/ 2 = 1939 $を返します。これは7で割り切れます。
  • $ p = 4621
    $はもっと難しいです。このためには、可能なすべての第四の力を確認する必要があります。しかし、四角形または四角形のいずれかが5で割り切れることに注意することで、少し簡単にすることができます(編集:これは実際に簡単です;
    mod 16を見てください:すべての四角形は0,1,4または9 mod 16、 4番目の累乗は0または1 mod
    16なので、それらの和は13 mod 16ではなく4621 = equiv 13 mod 16 $)
  • $ p = 5737 $は$(p + 1)/ 2 = 2869 $を返します。これは19で割り切れます。
  • $ p = 6481 $は$(p + 1)/ 2 = 3241 $を返します。これは7で割り切れます。
  • $ p = 7597 $は$(p + 1)/ 2 = 3799 $を返します。これは29で割り切れます。
  • $ p = 8341 $は19で割り切れます。
  • $ p = 9457 $は7で割り切れる。
  • $ p = 10201 $、$ 101 ^ 2 $と認識されます。
  • $ p = 11317 $は、最終的に満足します。

最も難しいことは、$ p = 11317 $と$ p = 5659
$がプライムであることを(手で)証明していますが、それ以外は実際に実行可能です。正直言って、私はプロセスで数の因子分解を使用しましたが、私が使った最大の素数は29だったので、手で行うことができます。

あるいは、$ p $を$ a ^ 2 + b ^ 4
$と書くことができるかどうかを確認するために、毎秒4度のパワーをチェックすることもできます。
$ 10 ^ 4 = 10000 $の下には10個しかないので、それも実行可能でなければなりません。

返信を残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です