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.1 回答者： R_Earl 回答日時： 2010/10/04 21:54

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

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