m[sup]p-1[/sup]≡1　(mod p)　⇒　m[sup]p-1[/sup]-1は pで割り切れる[br]m[sup]q-1[/sup]≡1　(mod q)　⇒　m[sup]q-1[/sup]-1は qで割り切れる[br]では、mod (p·q)にするにはどうしたら良いか？[br]　つまりpでもqでも割り切れる数は？[br][br]m[sup](p-1)(q-1)[/sup]-1を考えてみると、[br](m[sup](p-1)[/sup])[sup](q-1)[/sup]-1は qで割り切れる。[br](m[sup](q-1)[/sup])[sup](p-1)[/sup]-1は pで割り切れる。[br]よってm[sup](p-1)(q-1)[/sup]-1は p·qで割り切れる。（p·q=nとおく）⇒　m[sup](p-1)(q-1)[/sup]≡1　(mod n)[br]ここで、（　　）≡m　にするために、両辺にmをかける。[br]m[sup](p-1)(q-1)[/sup]·m≡m　(mod n)[br]m[sup](p-1)(q-1)+1[/sup]≡m　(mod n)[br]この時、(p-1)(q-1)+1＝e·dとすると、(m[sup]e[/sup])[sup]d[/sup]≡m　(mod n)となる。[br][br]