数学の予想をでっち上げる会コミュの倭奴のでっちあげ第7弾「素数判定式」

今朝、暇をもてあまして素数判定式を考えてたら
冗談のような素数判定式ができてしまったｗ
真偽が定かではないので、証明もしくは反証をお願いします。

　a is prime number if 2 ＝ 2^a (mod a), a > 2
　a is composite number if 2 ≠ 2^a (mod a), a > 2

要は任意の自然数a(> 2)に対し、
　2^a (mod a)で得られる値が2の場合aは素数、
　2^a (mod a)で得られる値が2以外なら合成数、
という判定式です。
これがただのでっち上げなら笑えるんですが
ちょっと冗談にしてはできすぎ？ｗｗｗ

コメント(6)

最初
全て
最新の40件

[1] mixiユーザー 09月29日 01:47

ちなみに上記の判定式を一般化してみたのが以下のようなもの
（pは任意の素数です）
a is prime number if p ＝ p^a (mod a), a > 2p
a is composite number if p ≠ p^a (mod a), a > 2p

これはちょっと怪しいですが、
なにせ値が指数関数的に増大するので、
パソコンの電卓じゃどうしようもなく、
判定どころではないのですよｗ

[2] mixiユーザー 10月01日 11:50

たぶん証明が出来たと思うので、今夜証明書いてみます。
新しい「でっちあげ」を考えているのですが…。
なかなかできないです。

[3] mixiユーザー 10月01日 18:38

さすが、えっくすあいずさん。
証明に手も足も出ない倭奴とは大違いですな。
感謝です。

ところで、いま素数判定法について、ググって見たら
AKS素数判定法なるものを発見しました。
こっちのほうが判定法では優秀そうですね。
だって多項式時間内だもん。

↓これってどう見ても、指数関数……orz
2 ＝ 2^a (mod a)
しかも正しいかどうかも分からないし……。

[4] mixiユーザー 10月01日 22:33

2 ＝ 2^a (mod a)　…?
?を変形して、?を作ると、
2^a / a = 2ax + 2　…?
ただし、xはpを一つ当てはめると、一意に決まる整数。
（つまり、2^aをaで割ったら、2aの倍数に2を足した値に等しい）

?の両辺にaをかけると、
2^p = 2x(p^2) + 2p　…?

（フェルマーの小定理の説明。ご存知の方は飛ばして読んでもらって可）
※p を素数とし、a を p の倍数でない整数（a と p は互いに素）とするときに、
a^(p-1) mod p = 1
すなわち a を p - 1 乗したものを p で割ったあまりは 1 になるというもの。

次に、フェルマーの小定理を変形して、
a^(p-1) / p = px + 1
(a^p) / (ap) = px + 1　…?
?のaに2を代入すると、
(2^p) / (2p) = px + 1
2^p = 2x(p^2) + 2p　…?

これで、?の式と?の式は一致する。
つまり、?の式は、フェルマーの小定理のa=2の場合に相当する。
よって、本問で問われている式は、常に成り立つと言える。

分かりにくい部分があれば返答願います。

[5] mixiユーザー 10月03日 00:56

ごめん。ちょっと描き方が間違ってたようなので訂正。
2 = 2^a(mod a)じゃなくて
2 (mod a) = 2^aだったみたい。
（もしくは2 (mod a) ≡ 2^aね）
うん。それだけｗ

それと、質問です。
(混乱するとあれなので、あえて2 = 2^a (mod a)を使います)
2 = 2^a (mod a)から
2^a / a = 2ax + 2への変形の仕方が分からないッすorz

実はあのあと、2 = 2^a (mod a)が
フェルマーの小定理に似ていることに気づいて（遅すぎ！ｗ）
カーマイケル数で試したら、見事ビンゴ！
まさしくでっち上げの極みですな。

まあ、また懲りずにでっちあげを考えるので暇だったら付き合ってくださいm(_ _)m

[6] mixiユーザー 10月06日 05:25

>2 = 2^a (mod a)から
>2^a / a = 2ax + 2への変形の仕方が分からないッすorz

これは、Ａ÷Ｂ＝Ｃ　余りＤ　（例、15÷4＝3…3）
の式を変形すると、Ａ＝Ｂ×Ｃ＋Ｄ　（例、15＝4×3＋3）
なりますよね。
2 = 2^a (mod a)は、２のａ乗をａで割った余りが２ですから、
上記式の、Ａは２のａ乗、Ｂはａ、Ｄは２となります。
Ｃに相当する部分は、２のａ乗の倍数になりますので、ｘをつけて、２ａｘとしているだけです。

ログインすると、みんなのコメントがもっと見れるよ