MENU
159,245

スレッド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回目たで、やりたした。の問題たでかなり先がありそうです。

たず、玠数 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