MENU
158,683

スレッドNo.859

フェルマーのぐるぐる小定理

ちょっと面白いことを思いつきました。
以下のような操作をしてみてください。

まず、素数 p およびそれと互いに素な自然数 a を決めてください。
手計算でやるなら p は 3 か 5 か 7 、a は 2 以上で a*p が 100 を超えないくらいがいいと思います。
コンピュータでやる場合は好きな大きさの数でご自由にどうぞ。

1, 1+p, 1+2p, ……, 1+(a-1)p の中から自由に 1 つ選んでください。
つまり「p で割ると 1 余る数を a*p 以下の自然数で 1 つ選んでください」ということです。

p > 2 であれば、
2, 2+p, 2+2p, ……, 2+(a-1)p の中から自由に 1 つ選んでください。
さっきのやつの余り 2 バージョンです。

p > 3 であれば、
3, 3+p, 3+2p, ……, 3+(a-1)p の中から自由に 1 つ選んでください。
余り 3 バージョンです。

以下余りを 1 ずつ増やしながら繰り返して、余り (p-1) バージョンまで実行してください。

これによって、a*p 以下の自然数を p-1 個選び出しましたね。
では、それらを小さい順に並べて一つの組としてください。

小さい順に並んでいる p-1 個の数の組に、以下のような 3 つの手順からなる操作 R をします。
まず、末尾に a*p を付け加え、一時的に p 個組とします。
先頭の数をしっかり覚えた上で切り落として、p-1 個組に戻します。
p-1 個の数それぞれからさっき切り落とした数を引き算します。

さて、では。

(1) 新しくできた p-1 個の数の組ですが、実は最初の組の作り方の条件に当てはまっていますね?
すなわち、
・a*p 以下の自然数 p-1 個が小さい順に並んでいる
・p で割った余りは 1 から p-1 まで 1 個ずつ
になっていますね?

(2) ということは、新しくできた組に対して操作 R をもう一度行うことができます。
そしてできた組にまたもう一度、さらにもう一度。
操作 R を p 回繰り返したとき、何かが起こると思いますが、それは何でしょう。

(3) 最初の組を新たに作り直し、再び操作 R を p 回繰り返してみてください。
あるいは、3 つめ、4 つめの組を作って、それらでも。
ほとんど全ての組で同じ現象が起こることを確認してください。

(4) 「全ての組」ではなく「ほとんど全ての組」と言ったのは、実は a と p が互いに素だと 1 つだけ例外があるからです。さて、それはどんな組で、何が起こるでしょう?

(5) これまでの実験で、最初の条件を満たすような p-1 個組の総数が、p の倍数 +1 個あることが納得してもらえたと思います。
ところで、最初の数の選び方をよく思い出して、このような p-1 個組って何通りあるんでしたっけ?

引用して返信編集・削除(未編集)

DD++様、おはようございます。

ニュートンのプリンキピアは、文章ばかりで、数式はなかったそうです。それを現代私達が習う物理学が数式中心ですが、それはオイラーの業績の1つだそうです。

さて、DD++様も文章ばかりでなく、数式をちらばせて、書いてくださるともっとわかりやすくなるんじゃないかな?と思います。

なんとかならないものでしょうか?

引用して返信編集・削除(未編集)

この話題、数式は引き算と掛け算と剰余しか出てきません。

掛け算 a*p は書いてます。
剰余 k+np も全部書いてます。
引き算は、文章中に 1 回しか登場しませんが、これもいちいち書いたほうがいいですか?

これら以外、書きたくても計算が存在しません。

引用して返信編集・削除(未編集)

こうなりました。どこで、間違えたのでしょう?
*************************************
まず、素数 p およびそれと互いに素な自然数 a を決めてください。
手計算でやるなら p は 3 か 5 か 7 、a は 2 以上で a*p が 100 を超えないくらいがいいと思います。
コンピュータでやる場合は好きな大きさの数でご自由にどうぞ。

1, 1+p, 1+2p, ……, 1+(a-1)p の中から自由に 1 つ選んでください。
つまり「p で割ると 1 余る数を a*p 以下の自然数で 1 つ選んでください」ということです。

1+r1p (mod p)≡1

p > 2 であれば、
2, 2+p, 2+2p, ……, 2+(a-1)p の中から自由に 1 つ選んでください。
さっきのやつの余り 2 バージョンです。

2+r2p (mod p)≡2

p > 3 であれば、
3, 3+p, 3+2p, ……, 3+(a-1)p の中から自由に 1 つ選んでください。
余り 3 バージョンです。

3+r3p (mod p)≡3

以下余りを 1 ずつ増やしながら繰り返して、余り (p-1) バージョンまで実行してください。

(p-1)+r(p-1)p (mod p)≡p-1

これによって、a*p 以下の自然数を p-1 個選び出しましたね。
では、それらを小さい順に並べて一つの組としてください。

{r1,r2,r3,r4,r5,r6,・・・,r(p-1)}

小さい順に並んでいる p-1 個の数の組に、以下のような 3 つの手順からなる操作 R をします。

まず、末尾に a*p を付け加え、一時的に p 個組とします。
{r1,r2,r3,r4,r5,r6,・・・,r(p-1),a*p}

先頭の数をしっかり覚えた上で切り落として、p-1 個組に戻します。
{r2,r3,r4,r5,r6,・・・,r(p-1),a*p}

p-1 個の数それぞれからさっき切り落とした数を引き算します。
{r2-r1,r3-r1,r4-r1,r5-r1,r6-r1,・・・,r(p-1)-r1,a*p-r1}

さて、では。

(1) 新しくできた p-1 個の数の組ですが、実は最初の組の作り方の条件に当てはまっていますね?
すなわち、
・a*p 以下の自然数 p-1 個が小さい順に並んでいる
・p で割った余りは 1 から p-1 まで 1 個ずつ
になっていますね?

----あれ、ちがうなあ。

引用して返信編集・削除(未編集)

「それらを小さい順に並べて一つの組としてください」

のところですね。
選んだ数は rk じゃなくて、k+rk*p の方です。
具体的な数でやらないと、ここの「小さい順」を並べるのは難しいと思いますよ。

引用して返信編集・削除(編集済: 2023年04月11日 15:11)

これによって、a*p 以下の自然数を p-1 個選び出しましたね。
では、それらを小さい順に並べて一つの組としてください。

{1+r1p,2+r2p,3+r3p,4+r4p,5+r5p,6+r6p,・・・,(p-1)+r(p-1)}

小さい順に並んでいる p-1 個の数の組に、以下のような 3 つの手順からなる操作 R をします。

まず、末尾に a*p を付け加え、一時的に p 個組とします。
{1+r1p,2+r2p,3+r3p,4+r4p,5+r5p,6+r6p,・・・,(p-1)+r(p-1),a*p}


先頭の数をしっかり覚えた上で切り落として、p-1 個組に戻します。
{2+r2p,3+r3p,4+r4p,5+r5p,6+r6p,・・・,(p-1)+r(p-1),a*p}

p-1 個の数それぞれからさっき切り落とした数を引き算します。
{2+r2p-(1+r1p),3+r3p-(1+r1p),4+r4P-(1+r1p),5+r5p-(1+r1p),6+r6p-(1+r1p),・・・,(p-1)+r(p-1)p-(1+r1p),a*p-(1+r1p)}

さて、では。

(1) 新しくできた p-1 個の数の組ですが、実は最初の組の作り方の条件に当てはまっていますね?
すなわち、
・a*p 以下の自然数 p-1 個が小さい順に並んでいる
・p で割った余りは 1 から p-1 まで 1 個ずつ
になっていますね?

---はい。これで、指示の手順は、あってますね。

ここから、実際の数で、問題を進めるわけですね?

引用して返信編集・削除(未編集)

いえ、選んで並べるところから具体的な数でどうぞ。

はちべえさんは 1+r1*p を最小値としていますが、実際は r1 と r2 の大小によっては
2+r2*p < 1+r1*p
となる場合もあり、必ずしも 1+r1*p が先頭にいるわけじゃないので。

引用して返信編集・削除(未編集)

はちべえさんがおっしゃるに
>ニュートンのプリンキピアは、文章ばかりで、数式はなかったそうです。それを現代私達が習う物理学が数式中心ですが、それはオイラーの業績の1つだそうです。

まあこのあたり、多くの高名な学者さんが関わっていますので……

御参考までに。


有賀 暢迪, 科学史入門 18世紀ヨーロッパの力学研究 : 学者たちの交流と論争, 科学史研究, 2014-2015, 53 巻, 272 号, p. 473-, 公開日 2020/12/14, Online ISSN 2435-0524, Print ISSN 2188-7535, https://doi.org/10.34336/jhsj.53.272_473
, https://www.jstage.jst.go.jp/article/jhsj/53/272/53_473/_article/-char/ja

引用して返信編集・削除(未編集)

途中まで作業していたらしいはちべえさんがその後どうなったのかわかりませんが、数日経ちましたので結局これが何だったのかというネタバラシを。
まあ、タイトルで最初からほとんど書いていたようなものですが。

実はこれ、フェルマーの小定理を、「個数」を使うことで式変形なしに直接証明できないかと試みたものです。

最初に提示した数の選び方は全部で a^(p-1) 通りあります。
このうち、全ての選択で a の倍数を選んだ { a, 2a, 3a, ……, (p-1)a } という組は唯一操作 R で自分自身になります。
(a と p が互いに素のとき、この選び方が必ず可能)

そして残りの a^(p-1) - 1 個の組は、同じ条件を満たす別の組を順に巡って「2 以上の p の約数」回後に自分自身に帰ってきます。
しかし、p は素数なので、「2 以上の p の約数」は p 以外にありません。
つまり、この操作 R でぐるぐると繋がる関係 p 個 1 グループに a^(p-1) - 1 個のものがもれなくダブりなく分けられます。

よって、a が p と互いに素であれば、a^(p-1) - 1 は p の倍数であることが示され……た、というほどきちんと書いてはいませんが、なるほど確かに成り立ちそうだと言えるくらいのオモチャができました。


……ということなのでした。
みなさんも「何か a^(p-1) 個のものを用意して、そこから 1 つを取り除くと、残りが漏れなく p 個ずつのグループにわけられる」ようなものを思いついたら是非教えてください。
実際にやってみると、簡単に作れそうに見えてめちゃくちゃ難しいです。

引用して返信編集・削除(未編集)

DD++様、こんばんは。

昨日、1回目まで、やりました。(2)の問題までかなり先がありそうです。
*******************************
まず、素数 p およびそれと互いに素な自然数 a を決めてください。
p=7 a=5 とします。

 1, 1+p, 1+2p, ……, 1+(a-1)p の中から自由に 1 つ選んでください。
1+3p=22

 2, 2+p, 2+2p, ……, 2+(a-1)p の中から自由に 1 つ選んでください。
2+2p=16

 3, 3+p, 3+2p, ……, 3+(a-1)p の中から自由に 1 つ選んでください。
3+2p=17

 4, 4+p, 4+2p, ……, 4+(a-1)p の中から自由に 1 つ選んでください。
4+3p=25

 5, 5+p, 5+2p, ……, 5+(a-1)p の中から自由に 1 つ選んでください。
5+2p=19

 6, 6+p, 6+2p, ……, 6+(a-1)p の中から自由に 1 つ選んでください。
6+2p=20

これによって、a*p 以下の自然数を p-1 個選び出しましたね。
では、それらを小さい順に並べて一つの組としてください。
{16,17,19,20,22,25}

小さい順に並んでいる p-1 個の数の組に、以下のような 3 つの手順からなる操作 R をします。

まず、末尾に a*p を付け加え、一時的に p 個組とします。
{16,17,19,20,22,25,35}

先頭の数をしっかり覚えた上で切り落として、p-1 個組に戻します。
{17,19,20,22,25,35}

p-1 個の数それぞれからさっき切り落とした数を引き算します。
{1,3,4,6,9,19}

さて、では。

(1) 新しくできた p-1 個の数の組ですが、実は最初の組の作り方の条件に当てはまっていますね?
すなわち、
・a*p 以下の自然数 p-1 個が小さい順に並んでいる
・p で割った余りは 1 から p-1 まで 1 個ずつ
になっていますね?
{1,3,4,6,9,19}≡{1,3,4,6,2,5}(mod p=7)

(2) ということは、新しくできた組に対して操作 R をもう一度行うことができます。
そしてできた組にまたもう一度、さらにもう一度。
操作 R を p 回繰り返したとき、何かが起こると思いますが、それは何でしょう。
(1)
{1,3,4,6,9,19,35}

{3,4,6,9,19,35}

{2,3,5,8,18,34}

{2,3,5,8,18,34}≡{2,3,5,1,4,6}(mod p=7)

(2)

{2,3,5,1,4,6}
{1,2,3,4,5,6}

{2,3,4,5,6,35}

{1,2,3,4,5,34}}≡{1,2,3,4,5,6}(mod p=7)

(3)
{1,2,3,4,5,6,35}

{2,3,4,5,6,35}

{1,2,3,4,5,34}≡{1,2,3,4,5,6}(mod p=7)

(4)
{1,2,3,4,5,6}

{1,2,3,4,5,6}

{2,3,4,5,6,35}

{1,2,3,4,5,34}}≡{1,2,3,4,5,6}(mod p=7)

(5)
{1,2,3,4,5,6}

{1,2,3,4,5,6}

{2,3,4,5,6,35}

{1,2,3,4,5,34}}≡{1,2,3,4,5,6}(mod p=7)
(6)
{1,2,3,4,5,6}

{1,2,3,4,5,6}

{2,3,4,5,6,35}

{1,2,3,4,5,34}}≡{1,2,3,4,5,6}(mod p=7)
(7)
{1,2,3,4,5,6}

{1,2,3,4,5,6}

{2,3,4,5,6,35}

{1,2,3,4,5,34}}≡{1,2,3,4,5,6}(mod p=7)

答え
{1,2,3,4,5,6}(mod p=7)
***************************
まちがってます?

引用して返信編集・削除(編集済: 2023年04月14日 18:59)

「1 回目の結果」は {2,3,5,8,18,34} ですよ。

引用して返信編集・削除(未編集)

あ、(2) の 1 回目、つまり全体の 2 回目の結果のことです。

引用して返信編集・削除(未編集)

>(2) ということは、新しくできた組に対して操作 R をもう一度行うことができます。
そしてできた組にまたもう一度、さらにもう一度。
操作 R を p 回繰り返したとき、何かが起こると思いますが、それは何でしょう。

これをやったつもりでしたが・・・・

間違ってましたか?

>(3) 最初の組を新たに作り直し、再び操作 R を p 回繰り返してみてください。
あるいは、3 つめ、4 つめの組を作って、それらでも。
ほとんど全ての組で同じ現象が起こることを確認してください。

で、これはどうなるんだろうと止まったのです。

引用して返信編集・削除(編集済: 2023年04月14日 20:06)

{1,3,4,6,9,19,35} <- 最後に 35 をつけた(操作 R の 1 つめ)

{3,4,6,9,19,35} <- 1 を切り落として(操作 R の 2 つめ)

{2,3,5,8,18,34} <- 全部から 1 を引いたら完成(操作 R の 3 つめ)

{2,3,5,8,18,34}≡{2,3,5,1,4,6}(mod p=7) <- 余りがバラバラか確認しただけ

さて、操作 R の完成品はどれでしょう?
本当に {2,3,5,1,4,6} ですか?

引用して返信編集・削除(未編集)

もう 1 回操作 R の定義をきちんと読んでください。

引用して返信編集・削除(未編集)

>小さい順に並んでいる p-1 個の数の組に、以下のような 3 つの手順からなる操作 R をします。
まず、末尾に a*p を付け加え、一時的に p 個組とします。
先頭の数をしっかり覚えた上で切り落として、p-1 個組に戻します。
p-1 個の数それぞれからさっき切り落とした数を引き算します。

でしたね。

とすると、
>{2,3,5,8,18,34} <- 全部から 1 を引いたら完成(操作 R の 3 つめ)
でしょうか?

引用して返信編集・削除(未編集)

はい、それが操作 R の結果です。
ですから、次は {2,3,5,8,18,34} から出発になります。

引用して返信編集・削除(未編集)

(1)
{1,3,4,6,9,19,35}

{3,4,6,9,19,35}

{2,3,5,8,18,34}

(2)
{2,3,5,8,18,34}

{3,5,8,18,34,35}

{1,3,6,16,32,33}

(3)
{1,3,6,16,32,33}

{3,6,16,32,33,35}

{2,5,15,31,32,34}

(4)
{2,5,15,31,32,34}

{5,15,31,32,34,35}

{3,13,29,30,32,33}

(5)
{3,13,29,30,32,33}

{13,29,30,32,33,35}

{10,26,27,29,30,32}

(6)
{10,26,27,29,30,32}

{26,27,29,30,32,35}

{16,17,19,20,22,25}
(7)
{16,17,19,20,22,25}

{17,19,20,22,25,35}

{1,3,4,6,9,19}

答え
{1,3,4,6,9,19}
これで、あってますよね?

引用して返信編集・削除(未編集)

はい、各回でやっていることはあっています。

ただ、{16,17,19,20,22,25} から {1,3,4,6,9,19} を作ったのが 1 回目ですから、

> (6)
> {10,26,27,29,30,32}
> {26,27,29,30,32,35}
> {16,17,19,20,22,25}

が 7 回目で、ここでストップです。

引用して返信編集・削除(未編集)

このスレッドに返信

ロケットBBS

Page Top