余りと、余りの２乗の余りが一致する個数

質問

まず、自然数Ｎで割ります。
すると、その余りは０～Ｎ－１までのＮ通りあります。
次に、その余りを二乗します。
そして、それぞれを再びＮで割ります。
そのとき、余りが、前の余りと同じになる個数が２のＭ乗あります。
そのＭは自然数Ｎを素因数分解したときの素数の種類の個数と一致します。

例えばＮ＝１０（＝２×５）のときは二つの余りが一致するのは０、１、５、６の、４個存在します。これはＮの素数の種類が２と５であるため、２の２乗と一致します。

しかし、なぜこのようなことがいえるのか、わかりません。また、もしかしたら、これはすべてにおいてはいえないかもしれません。
ですから、この証明、もしくは反例を教えていただけたらと思います。

回答No.4

pori_boy · ベストアンサー

0≦x<N として条件を満たすxを探します。
与えられた条件 x^2 (mod N) = x を変形すると

x(x-1) = aN (aは0以上の整数) となります。

ここで重要な性質として、「xとx-1の両方が
同じ数の倍数となることはない」を利用します。
つまり、Nが8の倍数という場合だと、必ず
xかx-1のいずれかが8の倍数となり、一方が2の
倍数で、もう一方が4の倍数というのはありません。

さて、1つの例として N=2^2 * 3 = 12
を考えてみます。

このとき、xとx-1の候補としては
x: -- x-1: 2^2 * 3 の倍数 (1)
x: 2^2 の倍数 x-1: 3 の倍数 (2)
x: 3 の倍数 x-1: 2^2 の倍数 (3)
x: 2^2 * 3 の倍数 x-1: -- (4)

つまり、2^2 の候補があります。
これは一般的にNを素因数分解したときの
素数の種類数をkとすると2^kとなります。

残りの証明は、各候補に対してちょうど1つ
うまくいくようなxが存在することを示します。
＃ちょうど1つ示すために、2つ以上存在しないこと
　1つは存在することを示すことになると思います

証明はここには書きませんが、上の例だと
(1) x=1 (x-1=0)
(2) x=4 (x-1=3) x^2 = 16 = 12 + 4
(3) x=9 (x-1=8) x^2 = 81 = 12*6 + 9
(4) x=0

とちょうど1つずつあることが確認できます。

お礼

回答ありがとうございます。
少しわかったような気がします。
本当にありがとうございます。
各候補に一つずつうまくいくｘがあるかどうかはわかりませんが、きっとあるのでしょう。

回答No.3

noname#48504

すみません。最後だけ間違えました。
M ≠ 1 ですね。

回答No.2

noname#48504

こんにちは。結論から言うと、一般には成立しません。
（反例）N が素数のとき。
p を N で割ったあまりを q とすると、q = 0 , ... , N - 1 で、なおかつ q と N は互いに素だから、q^2 と q が N で割って同じ余りになるなら、q と 1 を N で割っても同じあまり。（合同式を使うことで示される。）また、q を 0 から N - 1 まで動かすと、q^2 も 0 から N - 1 まで動く。したがって、この条件を満たす q は 1 のみ。このとき、M = 0 だが、素因数の種類は N の 1 種類だから、M ≠ N。

こんなもんでいかがでしょうか。参考になれば幸いです。

お礼

回答ありがとうございます。
しかし、素数のときは、q=1だけでなく、q=0のときも条件を満たすと思うのです。だから、q=0、1で2個存在します。だから、M=1になると思います。いかがでしょうか？

回答No.1

Tacosan

10 を例にしているんだけど, 0, 1, 5, 6 を 2 と 5 のそれぞれで割ったときに余りを考えるのがはやいかと思いつつ:
任意の素数 p と整数 n≧1 に対して x^2 ≡ x (mod p^n) ⇔ x ≡ 0 or 1 (mod p^n) を証明しておいて中国剰余定理かな?
前半の証明は, n = 1 のときは x^2 ≡ x (mod p) より x^2 - x ≡ 0 (mod p) より x^2 - x = x(x-1) = ap (a ∈ Z) とおけて p が素数であることから x ≡ 0 or 1 (mod p) でなければ x(x-1) が p を因数として持たないこと, n > 1 のときは x^2 - x = x(x-1) = ap^n (a ∈ Z) とおいて x と x-1 がともに p^n を因数に持たないと仮定すると x と x-1 が p を公約数に持つことになって矛盾する, ってやるかな.

お礼

中国剰余定理、知らなかったです。
これから勉強したいと思います。まだ理解が…。