合同式の問題がわかりません

質問

数学者目指してる大学生です。今代数学を独学している最中なのですが、そこで巡回群と生成元に関する証明に合同式が使われていました。どういうのかというと、
ij≡1(mod.n)⇒(i,n)=1(iとnの最大公約数が1)と言うものです。ちなみにi,j,n全て整数です。
合同式はかじってはいましたがこういうパターンは今まで見たことがなかったので苦戦しています。これが成立する理由を明確に教えてください。よろしくお願いします。セミナーで発表しないといけないので急ぎでお願いします。

回答No.2

noname#14584 · ベストアンサー

背理法．

(i,n)＝a(≠1)と仮定．
仮定より，
a|ij (1)
a|n (2)
一方，
ij-1|n (3)

(2)(3)及びa|iに留意することより，
a|ij-1 (4)

(1)(4)より，
a=1となって矛盾．

では，セミナー頑張ってくださいね．

＊より一般的な結果として＊
kx≡l(modm)
d|lの時だけ解を持ち，その個数は(k,m)個．

これを使ってもすぐ分かります．（証明は考えるか調べるかして下さい）

お礼

ありがとうございました。とてもわかりやすかったです。まだまだ未熟者ですが頑張ってやれるだけやってみます。便利な公式も教えていただきありがとうございました。

回答No.3

ojisan7

No.1さんとNo2さんの回答で良いと思います。これは、整数の最も基本的な性質だとおもいます。一般的には、
aZ+bZ=dZ⇒(a,b)=d　
が成り立ちますね。これは、大切です。覚えておきましょう。

お礼

回答ありがとうございます。よく覚えておきます。これでセミナーに間に合います、皆さんありがとうございました！

回答No.1

noname#48504

こんばんは。

i と n の最大公約数が d ≧ 2 と仮定してみてはいかがでしょう。i = d i_0 , n = d n_0 (i_0 , n_0 は整数)　となって、仮定の合同式は成立しません。（背理法）

それでは、セミナー頑張って下さい。

お礼

i_0などの表記が、勉強不足なものでちょっとわかりませんが、ｄが2以上と仮定して背理法ですね。やってみます。回答ありがとうございます。