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

質問

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の場合です)。

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

回答No.6

alice_44 · ベストアンサー

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 についても、同様。

補足

何度も回答いただき、ありがとうございます。

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

今回の私の質問は{(p-1)(q-1)+1}乗でしたが
(p-1)(q-1)乗の場合はどうすれば良いのでしょう?
pqで割った余りは1になってしまいませんか?

回答No.11

alice_44

p と q が互いに素でありさえすれば、
(A≡B mod pq) ⇔ (A≡B mod p かつ A≡B mod q)
は、成り立ちます。

(n が p と素でない) ⇒ (n は p の倍数)
を言うためには、p が素数であることを使います。
q についても同様。

回答No.10

alice_44

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 の倍数についても同様。

補足

ありがとうございました。

「≡n」を「n余る」のように思い込んでいました。
pとqが互いに素でありさえすれば、素数でなくても成り立つのでしょうか?

回答No.9

alice_44

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

補足

すみません、忘れていました。
p≠qの前提でお願いします。

回答No.8

Tacosan

(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 も条件に入れないとダメじゃない?

お礼

補足の補足です。

p≠qでお願いします。

＞n^{(p-1)(q-1)+1} ≡ n (mod p)
＞n^{(p-1)(q-1)+1} ≡ n (mod q)
どちらか一方は0だと思うのですが…。

補足

回答ありがとうございます。

すみません、高度すぎて
同型写像,iff,&などの用語、
また「結局」となる理由が分からないです。

回答No.7

alice_44

＞ 最後の「両辺に 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 と互いに素でないとき
でしたよね？

お礼

補足の補足です。
うまく私の意図が伝わらなかったと思うので…要点は以下の通りです。

pがnと互いに素であり、qがnと互いに素でないとき
　n^(q-1)(p-1) ≡ 1 (mod p)
　n^(q-1)(p-1) ≡ 0 (mod q)なのに
　n^(q-1)(p-1) ≡ 1 (mod pq) とは言えない。
となるのに
　n^{(q-1)(p-1)+1} ≡ n (mod p)と
　n^{(q-1)(p-1)+1} ≡ 0 (mod q)から
　n^{(q-1)(p-1)+1} ≡ n (mod pq) が言える。
という論法だと思うのですが、この違いは何なのですか?
nをかけたことで何が変わったのでしょうか?

補足

回答ありがとうございます。

＞難しいでしょうか。
それは分かるのですが、
pで割った余りがnと合同になることは
pqで割った余りがnと合同になることと同値なのでしょうか?

同値でないとしたら、何のためにnをかけたのかわかりません。

回答No.5

Tacosan

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

補足

回答ありがとうございます。

具体的にどうすれば良いのでしょうか?

回答No.4

R_Earl

簡単な例として、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

回答No.3

R_Earl

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

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

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

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

回答No.2

R_Earl

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

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

補足

回答ありがとうございます。

正にRSA暗号の勉強中なんです。

回答No.1

R_Earl

> p,qが素数のときn^{(p-1)(q-1)+1}≡n (mod pq)になりますか?

正しいです。

> n^{(p-1)(q-1)}≡1 (mod pq)は言えないものの
> n^{(p-1)(q-1)+1}≡n (mod pq)は言えてしまっているように思えます

n^{(p-1)(q-1)} ≡ 1 (mod pq)とならなくても、
もしnx ≡ 1 (mod pq)となるような整数xが存在すれば、

n^{(p-1)(q-1)}≡x (mod pq)
↓
n^{(p-1)(q-1)+1}≡ nx ≡ 1 (mod pq)

となります。

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

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

オイラーの定理無しでも示す事ができたような気がするのですが、
どうやったか忘れてしまいました。