＜問題＞

いえ、同値ではありません。"xEAならばxEB かつ xEBならばxEA"というのは、問題文下のヒントでいう四角の二番の考え方と同値です。ｘＥＡのとき、ｘをＡの「元」であるといいます。Ａの要素（この問題でいう１、２、３、・・・、Ｐ－１）は全て元です。

Ａ⊆Ｂ→Ａの元が全てＢに含まれると考える。（xEAならばxEB）

Ｂ⊆Ａ→Ｂの元が全てＡに含まれると考える。（xEBならばxEA）

集合論の問題で、Ａ＝Ｂを示すときはこの考え方がよく使われます。ただ、今回はこれとは違う解き方をしているようです。

さて、（２）です。

（２）の解答の最初に書いてある、「（ap + i）（bp + j）＝p（abp + aj + bi） + ij」というのは、

「（a1p + r1)（a2p + r2)・・・・・（ap-1 + rp-1)＝Ｎp　+　r1r2・・・rp-1」

が理解できるならば、読み飛ばしちゃってＯＫです。a、b、i、jが自然数ならば、「（ap + i）（bp + j）・・・」という形のものは、

（ap + i）（bp + j）・・・＝ｐ×（自然数）+　（定数項の積）

のように変形できるということの理解を助けるために書いてあるだけです。（定数項とは、上でいうi、jなどのことです。）

さて、（１）で証明したことを用いるために、nk＝ａkｐ + ｒkとおきます。nkをｐで割ったときの商をａk、あまりをｒｋと置いたわけですね。

ｋ＝１のとき、n・１＝ａ1ｐ + ｒ1

ｋ＝２のとき、n・２＝ａ2ｐ + ｒ2

となります。ここで、（２）の問題文で出てきている「ｎ＾（ｐ－１）」という形を作るために、

ｎ・１　×　ｎ・２　×　・・・・・　×ｎ・（ｐ－１）を計算します。

そうすると、a1~a(p-1)、r1~r(p-1)は全て自然数ですので、

「（a1p + r1)（a2p + r2)・・・・・（ap-1 + rp-1)＝Ｎp　+　r1r2・・・rp-1」

となります。（Ｎは自然数）

ここで、（１）より、ｒ1~ｒp-1というのは全て集合（ｒｋ｜ｋＥＡ）の元であり、Ａの全ての元と一致します。よって、r1r2・・・rp-1＝１・２・・・・・（ｐ－１）

となるわけですね。こういうことを用いて変形していくと、最終的に

（ｎ＾（ｐ－１）ー１）・１・２・・・・・（ｐ－１）＝Ｎｐ

となりました。右辺は（自然数）×ｐなので、ｐの倍数です。ということは、左辺もｐの倍数になっていなくてはなりません。つまり、左辺の素因数の中にｐが入っていなくてはならないのですが、ｐは素数です。２～（ｐ－１）まで、全てと互いに素です。よって、１・２・・・・（ｐ－１）だけではｐという素因数を作り出せません。だから、（ｎ＾（ｐ－１）ー１）がｐの倍数になっていなくてはならないのです。よって、（ｎ＾（ｐ－１）ー１）はｐで割り切れるということです。

結構難しい問題ですね！自分でも解答に自信がないです・・・。

(1)は、あまり見ない形の証明ですね。

ﾋﾝﾄを見ても何を言っているのか良く判らず、かなり考え込んでしまいました。

ﾋﾝﾄの前半にある通り、この解答では、｛rk｜kEA｝の要素をすべて求めて、それがAと完全に一致することを示す事によって、証明がなされています。

(通常は、要素をすべて求めるということはしないので、"xEAならばxEB かつ xEBならばxEA"を示して、一致するということを証明します。この解き方は珍しいと思います。)

解答の方に少し付け加えるとすると、

(青下線の)それぞれ相異なるP-1個の値をとる、という文章の後に、

従って、｛rk｜kEA｝は、1～P-1までのすべての数の集合である。

Aは、1～P-1までのすべての数の集合なので、

｛rk｜kEA｝＝A

となります。

これで少し判りやすくなりましたでしょうか。

ﾋﾝﾄで青丸で囲ってあるところは、集合が一致する（"xEAならばxEB かつ xEBならばxEA"と同値である）ことを証明するためのﾋﾝﾄではなく、｛rk｜kEA｝のすべての要素を求めるための背理法のﾋﾝﾄとして書かれているものです。

> "xEAならばxEB かつ xEBならばxEA"と同値になるのでしょうか？

ちょっと勘違いしていますね。

まるで囲ってある部分（以下○○○と書く）は、

「rkが1からp-1までの自然数の集合であることを証明するために、」

「○○○を使って証明することにしましょう！」

と方針を述べているだけです。

rkが「rkが1からp-1までの自然数の集合」ならば、その要素の中には

「ダブり」があってはいけないですよね。

ダブりがあるというのは

「rkの要素の中にri=rjとなる組み合わせがある。（ただしi≠jとする）」ということですから、

「rkが1からp-1までの自然数の集合」

⇔

「1からp-1までの自然数の集合rkの要素の中ではi≠jならば、かならずri≠rj」

となりますよね。

そこで、（１）ではri=rjと仮定すると矛盾が生じますよ！と証明しているわけです。

（２）はまた後ほど

高校数学の中でも地味に難しい整数論ですね。

>その解答例と青円を結びつけることがまだちょっとできません。青円は必要条件に過ぎないのではないでしょうか？

例えば二つの集合Ａ，Ｂが

Ａ＝{1,2,3}

Ｂ＝{a,b,c}

のとき、a,b,cが全て相異なること(つまりa≠b、a≠c、b≠c)は必要条件ですね。

なぜならばＡ＝ＢのためにはＡの要素数とＢの要素数が同じ必要があるからです。

しかしaもbもcも1～3のいずれかであることがわかっている場合、

a,b,cが全て相異なることはＡ＝Ｂの必要条件であり、また十分でもあることはおわかりでしょうか？

a,b,cが全て相異なれば、a,b,cの中に1と等しいものがあります。

1と等しいものが無いとするとa,b,cは2か3であり鳩の巣原理よりa,b,cの中に等しいものが存在してしまうからです。

同様にa,b,cの中に2と等しいものがあります。

さらに同様にa,b,cの中に3と等しいものがあります。

a,b,cは1～3のいずれかでしかないわけですからＡ＝Ｂとなります。

この(1)の問題も同様です。

Ａ＝{1,…,p-1}

Ｂ＝{r1,…,r(p-1)}

まずそれぞれのriはpで割った余りですので0以上p-1以下であることはわかっています。

またnもkもpと互いに素であることがわかっていますのでnkをpで割って余りが0となること(割り切れること)はありえません。

つまりそれぞれのriは1からp-1までの自然数のどれかであることがわかります。

ここまでわかっていればri≠rj(i≠j)を示せば必要かつ十分なのです。