モジュラ演算

質問

x(mod a)を引き算するのはa-x(mod a)を加えることによって実現出来る事を示せ、という問題があるのですが、問題の意味がよくわかりません。仮にzという数があるとすると、z-x(mod a) = z+(a-x(mod a))ということでしょうか？
でもそうすると、仮に5 mod 3 = 2、z = 10を考えると、10 - 2 ≠ 10 + (3 - 2)なので問題を取り違えていると思われます。おわかりの方いらっしゃったら教えて頂きたいです。変な質問ですみません。

回答No.2

arrysthmia · ベストアンサー

z + (a - x (mod a)) という書き方に、勘違いのヒントがありそうです。
x (mod a) は、x と a から何かの値を求める演算ではありません。
x を a で割った余りが x (mod a) ということではないのです。

y = x (mod a) という式は、「(y - x) は a の整数倍だ」という意味です。
(mod a) は、右辺の一部ではなく、式全体もしくは = に付属しています。
一個の x に対して、y = x (mod a) を満たす y は、
y = x, x±a, x±2a, x±3a, …　と無数にあります。
0 ≦ y ＜ a でなければならない理由も特にありません。

10 - 2 と 10 + (3 - 2) の差は 3 ですから、
10 - 2 = 10 + (3 - 2) (mod 3) は、成立しています。
「だって、8 ≠ 11 じゃん」という誤解を避けるために、
10 - 2 = 10 + (3 - 2) (mod 3) の替わりに
10 - 2 ≡ 10 + (3 - 2) (mod 3) と書くことも多いですね。
どちらでも、意味は同じですが。

z - x と z + (a - x) の差が a の倍数なので、
z - x = z + (a - x) (mod a) は、成立するのです。
0 ＜ x ＜ a である場合には、0 ＜ a - x ＜ a ですから、
a で割った余りの引き算が a で割った余りの足し算に置き換えられた
ようにも見えます。しかし、x = 0 の場合を考えてみれば、
そうではないことが分かります。

お礼

よくわかりました。そうすると、z-x = ak（kは整数）とすると、z+a-x = ak+a = a(k+1)、したがってaで割り切れるから成り立つ、といったところですよね。有り難うございました。

回答No.1

yumitsuki

おそらく、問題の意味は、
(z - x)(mod a) = (z + a - x)(mod a)
を示せ、ということだと思われます。

z < x の場合に、この手法が用いられます。

お礼

有り難うございました。