逆元の話 (6ページ目)

けんちょん @drken1215

「互いに素」だけで結構書ける気がするのん。例えば最大公約数が出て来る場面って、結局「互いに素」に帰着したいケースが多いし、互いに素という性質の理解は重要課題な気はするのん。蟻本の「線分上の格子点の個数」とかはその典型だと思うのん。

2018-05-04 01:55:56

keymoon @kymn_

@tempura_pp あーほんまじゃん(つら)(1が存在するということが言えればいいだけだったのでEuclidの互除法の応用で問題ないですね。)

2018-05-04 01:56:59

けんちょん @drken1215

その手の問題は、「互いに素」に帰着させれば解けるという部分が非自明になればなるほど、難しい問題ということになると思うのん。

2018-05-04 01:57:13

てんぷら @tempura_cpp

@kymn_ 1の存在はべき乗からも言えます(n,n^2,n^3,...はmodmで有限個の値しか取れないのでn^iとn^jが等しくなるようなi<jが取れて、このときn^(j-i)が1になる)

2018-05-04 01:58:58

けんちょん @drken1215

@mofpad まさにそこがすごく難しいですよね！！！！！人それぞれという部分が。。。個別に学部生さんの相談に乗る時は、学部生さんの感覚に合わせたりするのがすごく楽しいですよね！

2018-05-04 02:03:44

M @601________

互いに素の性質素数でない数mについて0=(x-a)(x-b) mod mは3個以上の解を取りうる（ｍが素数のときは成立しない）例えばa=1,b=2としたとき、(5-1)(4-2) mod 8 =4*2 mod 8 =0 mod 8となる。これは(x-a)、(x-b)がmと互いに素でなくなってしまうため。体と環の違い。

2018-05-04 02:26:20

M @601________

どんどん知識・技術がコモディティ化してほしい。

2018-05-04 02:27:35