p,qが素数のときn^{(p-1)(q-1)+1}≡n (mod pq

Question

p,qが素数のときn^{(p-1)(q-1)+1}≡n (mod pq)になりますか?
nがpともqとも互いに素であるときは、
Fermatの小定理を使えばn^{(p-1)(q-1)}≡1 (mod pq)
が言えるので、標記の命題は言えると思うのですが

pまたはqのいずれか一方がnと互いに素でないとき
n^{(p-1)(q-1)}≡1 (mod pq)は言えないものの
n^{(p-1)(q-1)+1}≡n (mod pq)は言えてしまっているように思えます
(私がやったケースはp=3,q=11の場合です)。

これは正しいのでしょうか?
正しいとしたら何故ですか?

alice_44 · Accepted Answer

p と q が互いに素なので、
与式が mod pq で成立することは、
同じ式が mod p と mod q の両方で成立する
ことと同値です。

p と q が素数であることから、
n は、p,q それぞれについて、
割り切れるか、互いに素であるか
のどちらかです。

n が p の倍数である場合、
両辺が ≡0 (mod p) になるので、
与式は mod p で成立します。

n が p と素な場合、
(n の q-1 乗) も p と素なので、
フェルマーの小定理より、
(n の q-1 乗) の p-1 乗 ≡ 1 (mod p) です。
両辺に n を掛ければ、
与式が mod p で成立することが解ります。

mod q についても、同様。

alice_44 · Answer

p と q が互いに素でありさえすれば、
(A≡B mod pq) ⇔ (A≡B mod p かつ A≡B mod q)
は、成り立ちます。

(n が p と素でない) ⇒ (n は p の倍数)
を言うためには、p が素数であることを使います。
q についても同様。

alice_44 · Answer

n を掛けた意味は、No.7 に書いたとおり、
左辺の指数を +1 して与式に合わせただけです。
他意はありません。

No.6 の冒頭に書いた「等式が mod pq で成立
⇔ 同式が mod p と mod q で成立」を
吟味してみて下さい。
No.6 No.7 ともに、コレを基本方針としています。

No.9 補足については、先の繰り返しになりますが、
p と q が素数であることから、
n が pq と素でなければ、
n は、p または q の倍数です。
n が p の倍数であれば、≡n (mod p) と
≡0 (mod p) は同値なので、
n×0 で悩む必要は、ないのです。
q の倍数についても同様。

alice_44 · Answer

ホントだ。
「p と q は互いに素」って、書いてない。
これは仮定しないと、成り立たないですね。

Tacosan · Answer

(a, b), (c, d) ∈ { 0, ..., p-1 } × { 0, ..., q-1 } に対し
(a, b) + (c, d) = ((a+c) mod p, (b+d) mod q),
(a, b) ・ (c, d) = (ac mod p, bd mod q)
で + と ・ を導入すると, 写像 f: x → (x mod p, x mod q) は { 0, ..., pq-1 } から { 0, ..., p-1 } × { 0, ..., q-1 } への同型写像. そして Chinese Reminder Theorem からこの写像は全単射なので結局
n^{(p-1)(q-1)+1} ≡ n (mod pq) iff n^{(p-1)(q-1)+1} ≡ n (mod p) & n^{(p-1)(q-1)+1} ≡ n (mod q).
右は簡単.
ああ, p = q だと破綻するので p ≠ q も条件に入れないとダメじゃない?

alice_44 · Answer

＞ 最後の「両辺に n を掛ければ」が分かりません。

n の (q-1)(p-1) 乗 ≡ 1 (mod p)　←[1] の両辺に n を掛けると、
n の { (q-1)(p-1)+1 } 乗 ≡ n (mod p)　←[2] になると思いますが…
難しいでしょうか。

No.6 では、「n が p と素な場合」に [1][2] を示しています。
「n が p の倍数である場合」には、[1] を経由せず、直接 [2] です。

n が p と素、かつ、n が q と素 であれば、[1] から
n の (q-1)(p-1) 乗 ≡ 1 (mod pq)　を示すことができますが、
質問の仮定は、
＞ p または q のいずれか一方が n と互いに素でないとき
でしたよね？

Tacosan · Answer

p, q が素数のとき写像 f: { 0, 1, ... , pq-1 } → { 0, 1, ..., p-1 } × { 0, 1, ..., q-1 }, x → (x mod p, x mod q) を考えるといいような気がする.

R_Earl · Answer

簡単な例として、n^{(p-1)(q-1)+1} ≡ n (mod pq)が
n = pの場合に成り立つ事を示します。

まずはじめにp^m ≡ p (mod pq)となるmの条件を考えます。
p^m ≡ p (mod pq)が成り立つなら、これを変形して

p^m - p ≡ 0 (mod pq)
∴ p(p^(m-1) - 1) ≡ 0 (mod pq)

となります。
つまりp(p^(m-1) - 1)はpqで割り切れます(つまりpqの倍数)。
p(p^(m-1) - 1)の左の因数がpなので、右の因数(p^(m-1) - 1)が素因数qを持たないと、
p(p^(m-1) - 1)はpqの倍数になりません。
よって

p^(m-1) - 1 ≡ 0 (mod q)
∴ p^(m-1) ≡ 1 (mod q)

となります。
よってp^(m-1) ≡ 1 (mod q)となる
mの条件を考えればよいことになります。
ここでFermatの小定理から、m-1 = q-1のときに
p^(m-1) ≡ p^(q-1) ≡ 1 (mod q)
となる事が分かります。同様にm-1 = k(q-1)の時も(kは整数)
p^(m-1) ≡ (p^(q-1))^k ≡ 1 (mod q)が成り立ちます。
以上よりm = k(q-1) + 1の時(つまりmが「(q-1)の倍数 + 1」の時)、
p^m ≡ p (mod pq)が成り立ちます。

よってmが(p-1)(q-1) + 1の時、
これもやはりmが「(q-1)の倍数 + 1」の形になっているので
p^m ≡ p (mod pq)が成り立つことになります。
つまりn^{(p-1)(q-1)+1} ≡ n (mod pq)はn = pでも成り立つ事になります。

n = qの場合や、nがpの倍数、qの倍数の場合の時も同様の方法で示せます。

参考URL：http://pgp.iijlab.net/crypt/rsa.html

R_Earl · Answer

ANo.1ですが、ANo.1の回答内容は間違ってました。

> Fermatの小定理と似た、「オイラーの定理」というものがあります。
> そちらを調べてみてください。

ここが誤りです。
オイラーの定理を使っても質問者さんの疑問は解決しません。
申し訳ありませんでした。

もし、以前示した方法を思い出したら、また書きます。

R_Earl · Answer

ANo.1ですが、言い忘れた事がありました。

n^{(p-1)(q-1)+1} ≡ n (mod pq)という式は、
暗号化に用いられています。
RSA暗号という方式では、この式を使って暗号化・復号化をしています。
なのでそちらの方面から調べてみるのもよいかもしれません。

p,qが素数のときn^{(p-1)(q-1)+1}≡n (mod pq

p と q が互いに素なので、

この回答への補足

p と q が互いに素でありさえすれば、

n を掛けた意味は、No.7 に書いたとおり、

この回答への補足

ホントだ。

この回答への補足

(a, b), (c, d) ∈ { 0, ..., p-1 } × { 0, ..., q-1 } に対し

この回答への補足

＞ 最後の「両辺に n を掛ければ」が分かりません。

この回答への補足

p, q が素数のとき写像 f: { 0, 1, ... , pq-1 } → { 0, 1, ..., p-1 } × { 0,

この回答への補足

簡単な例として、n^{(p-1)(q-1)+1} ≡ n (mod pq)が

ANo.1ですが、ANo.1の回答内容は間違ってました。

ANo.1ですが、言い忘れた事がありました。

この回答への補足

似たような質問が見つかりました

関連するカテゴリからQ&Aを探す

デイリーランキングこのカテゴリの人気デイリーQ&Aランキング

マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング

＞最後の「両辺に n を掛ければ」が分かりません。