隠し部屋の秘境

豆知識的な小ネタ見つけては投稿していきます

余り演算の性質

目次へ余り演算とは次のようなもの
a%b=aをbで割った余り
数学ではこの演算子よりも合同式を使われがちですが、コンピューター分野ではバリバリこっちです。
ただ、この％演算は処理しづらく、一度に複数組み込むと式が汚くなってしまいます。(処理すると可読性は下がります。注釈しましょう)
しかし、調べてみると便利な性質を持つようなのでまとめました。

結論から言うと次のような性質があります。
(名前は勝手につけました。ご指摘があればコメントよりお願い致しますm(_ _)m)

目次

  1. 基本則 a=[a/b]×b+a%b
  2. 周期性 (a+kb)%b=a%b
  3. 和の冪等性 (a+b)%c={(a%c)+b}%c
  4. 積の冪等性 (a×b)%c={(a%c)×b}%c
  5. 指数の冪等性 (a^b)%c={(a%c)^b}%c
  6. 分配法則 c(a%b)=ac%bc
  7. 商の余り [a/b]%c=(a%bc-a%b)/b
  8. 省略定理 (a%b)%c=a%b (b≦c)
  9. 短絡定理 (a%b)%c=a%c (bはcの倍数)
  10. 減法定理 (a-b)%a=(a-1)-(b-1)%a (1≦b

番外

今回は証明構造がユニークなので良い頭の体操になります。良ければ皆さんも考えてみてくださいね！

それでは解説を始めます

① a=[a/b]×b+a%b

まずは基礎です。前提の伝え合わせも兼ねておきます。
[x] : xを超えない最大の整数
→ここでは0≦xを想定して「切り捨て」の演算子として用いています

その上で、この式は
商×割る数 + 余り = 割られる数
を意味している事がわかると思います。
要は小学校の算数ですね。

当たり前っぽいですが一応基本方針の提示として証明しておきます。

割られる数をa, 割る数をb
商をQ, 余りをRとします。
この定義からは直接a÷b = Q…R が言えます。
すると(a-R)÷b = Q が言えます。
a-R = bQ ∴ a = bQ+R が言えました！
a÷b = Q…R ⇒ a = bQ+R です。
ここの式の変換が後の証明でも基本になってきます。

また、ここでは後はQ = [a/b] を示せば良いのですが、もう1つ重要なのが0≦余り＜割る数です。
続き
これより、\dfrac{a}{b}=Q+\dfrac{R}{b}となります。
ここで、
Qは整数より小数部分は0
\dfrac{R}{b}は0≦R＜b ∴ 0≦R/b＜1 より小数部分は\dfrac{R}{b}
よってa/bの小数部分はR/bとなるので、
a/bの切り捨ての値はa/b-R/b = Q
よって[a/b]=Q が言えました。
また、a%b=R は定義なので自明です。
以上をまとめると、
a = Qb+R
Q, Rに代入する
a = [a/b]×b + a%b [完]

今回は小数部分という考え方を用いましたが、商を吟味する場合にはこれも重要になってきます。ただ、余りに関する演算なため、商の議論は重要にならない事が殆どで滅多に必要ありません。

あと、これを逆に辿ると
続き
a=b[a/b]+a%b
∴ (a-a%b)/b=[a/b] ∴ (a-a%b)÷b=[a/b]…0
ここで、a%b=a-b[a/b]=b(a/b-[a/b]),
0≦a/b-[a/b]＜1 より
0≦b(a/b-[a/b])＜b ∴ 0≦a%b＜b が言えるので
a%bはbで割り切れないことが分かります。
a = (a-a%b) + a%b であり、a-a%bはbで割り切れるのでa%bだけ余ります。
以上よりa÷b=[a/b]…a%b
∴ a÷b=Q…R が言えました。[完]
これでa÷b = Q…R ⇐ a = bQ+R も言えたので
a÷b = Q…R ⇔ a = bQ+Rとなります。ちょっと無理矢理感がありますが。
▲閉じる
これは普通に青チャートとかにも載ってるので安心して使って大丈夫です。

② (a+kb)%b=a%b

kbはbの倍数を意味しています。
要するに割る数の倍数を足しても余りは変わらないことを表現しています。

割られる数をa, 割る数をb,
商をQ, 余りをRとします。
a÷b = Q…R ⇔ a = bQ+R
∴ a+kb = bQ+R + kb = b(Q+k) + R
∴ a+kb = b(Q+k) + R ⇔ (a+kb)÷b = (Q+k)…R
よってa%b = (a+kb)%b = R [完]
▲閉じる

詐欺的に%演算が出てきたと感じるかもしれません。
日本語に訳せば解決します。
aをbで割った余り、a+bcをbで割った余り、どちらもRになったということです。ここの対応が定着すれば大した事じゃないです。
ポイント
kbをQとまとめる発想と、それをまとめて商と見なせるかが鍵になってきます。代数学的なセンスが問われる所だと思います。

③ (a+b)%c={(a%c)+b}%c

先に和の要素の余りを計算しても最終的な余りは変わらないことを表現しています。

割られる数をa, 割る数をc,
商をQ, 余りをRとします。
a÷c = Q…R ⇔ a = cQ+R
これを代入すると
(a+b)%c = (cQ+R+b)%c
= (R+b)%c ∵ ②
= {(a%c)+b}%c ∵ a%c=R
以上より(a+b)%c={(a%c)+b}%c [完]
▲閉じる
①～③はだいたい同じような事を言っています。
ポイント
とりあえず律儀に、(a+b)÷c, a÷c, b÷c それぞれの商と余りを定義したところから始めたとしても、
a=cQa+Raなどをa+bに揃えた時点でおのずと答えが出たことと思います。
恐らくこれは殆どの人が解けたのではないでしょうか。

④ (a×b)%c={(a%c)×b}%c

先に積の要素の余りを計算しても最終的な余りは変わらないことを表現しています。

(a×b)%c={Σ(k=1→b)a}%c
={Σ(k=1→b)(a%c)}%c ∵ ③
={(a%c)×b}%c [完]
▲閉じる
これも殆どの人は出来たんじゃないだろうか？
ポイント
掛け算が足し算のかき集めである事を連想出来れば③が使えそうだと気づけます。

⑤ (a^b)%c={(a%c)^b}%c

数学の合同式でよく知られるやつです。合同式では、aの代わりは同位相であればなんでも良かったので若干意味が異なります。
しかしまあ、②をぶち込んでやればそちらも再現可能です

(a^b)%c={Π(k=1→b)a}%c
={Π(k=1→b)(a%c)}%c ∵ ④
={(a%c)^b}%c [完]
▲閉じる
ポイント
③の証明と全く同じ形ですね

⑥ k(a%b)=ka%kb

まさかの分配法則持ち演算子です。交換法則も結合法則もありません。分配法則だけです。

割られる数をa, 割る数をb,
商をQ, 余りをRとします。
cを任意の自然数とします。
a÷b = Q…R ⇔ a = bQ+R
∴ ka = kbQ + kR ⇔ ka÷kb = kbQ…kR
以上より
k(a%b) = ka%kb [完]
▲閉じる
証明見たら普通に当たり前なんですが、コイツが中々便利なんですわ
ポイント
実は出来心でa = bQ+Rの両辺にkをかけてたまたま発見しました。証明しようと思ってすると案外難しいのかもしれない。

⓪ [[a/b]/c]=[a/bc]

a,b,cは任意の自然数です。切り捨てを纏められる事を言っています。
％演算が不在ですが証明では便利なので挙げました。番号が⓪なのはもはや％演算の性質じゃないからです。

割られる数をa, 割る数をb, cとします。
aをbで割った余りをRbとします。
[a/b]をcで割った余りをRcとします。
①とa%b=Rbより a = b[a/b]+Rb
∴ a/bc = [a/b]/c + Rb/bc
= [[a/b]/c] + Rc/c + Rb/bc
ここで、
0≦Rb＜b
∴ Rb/bc ＜ 1/c
∴ Rc/c + Rb/bc ＜ Rc/c + 1/c = (Rc+1)/c
またRcは整数でありRcRc/c + Rb/bc ＜ 1 が分かります。
よって
[a/bc] = [[[a/b]/c] + Rc/c + Rb/bc]
= [[a/b]/c] [完]
▲閉じる
なっげぇぇぇぇぇぇ。。。短くならないんか！
ポイント
これ以外に思いついきませんでした。まじでエグいです。もっとスマートな証明考え中です。

⑦ [a/b]%c=(a%bc-a%b)/b

正直どう役に立つのか検討もつかないですが、証明するだけしてみましょうか。

割られる数をa, 割る数をb,cとします。
①より [a/b] = c[[a/b]/c] + [a/b]%c
∴ [a/b]%c = [a/b]-c[[a/b]/c]
= [a/b]-c[a/bc] ∵ ⓪
また、
a = b[a/b] + a%b
∴ [a/b] = (a-a%b)/b
a = bc[a/bc] + a%bc
∴ c[a/bc] = (a - a%bc)/b
以上より
[a/b]%c = [a/b] - c[a/bc]
= (a-a%b)/b - (a-a%bc)/b
= (a%bc-a%b)/b [完]
▲閉じる
さしずめこれもなんかの証明に使うんでしょうね。
ポイント
[a/b]%cの％演算を何とかしたかったので、無から％演算を生成する①を逆に辿ることで処理出来るのではないかと考えました。

⑧ (a%b)%c=a%b (b≦c)

ある数で余りを計算した後、それ以上の数で割っても余りは変わらないことを言っています。
意味的には当たり前ですね。証明してみましょう。

割られる数をa, 割る数をb,cとします。
bで割った余りをRbとします。
それをcで割った商と余りを
それぞれQc,Rcとします。
Rb÷c = Qc…Rc ⇔ Rb = cQc+Rc
ここで背理法を用います。
1≦Qcとすると、
b≦c
c≦cQc ∵ 1≦Qc, 0＜c
cQc=cQc+0≦cQc+Rc ∵ 0≦Rc
cQc+Rc=Rb
これらをまとめると、
b≦c≦cQc=cQc+0≦cQc+Rc=Rbとなり、
b≦Rbが導かれますが、
これは0≦Rb＜bに見事に矛盾する事が分かります。
よって1≦QcではないのでQc＜1となるのですが、Qcは0以上の整数なのでこれは0です。
よって
Rb=cQc+Rc ∴ Rb=c×0+Rc ∴ Rb=Rc
∴ a%b=(a%b)%c [完]
▲閉じる
まさかの証明出来ました。
①もそうでしたけど、当たり前な事を証明するのって難しいんですね。
ポイント
Rbをそれより大きなcで割る時点で商が出ない,すなわちQc=0となるのは予想できたので、それを証明するためにQc=0以外の場合では何かしら不都合が生じるはずだと予想できました。背理法まっしぐらです。

⑨ (a%b)%c=a%c (bはcの倍数)

倍数なら上書き出来るという事です。(説明雑)

割られる数をa, 割る数をb,cとします。
aをbで割った商と余りを
それぞれQ, Rとします。
また、b=kcとします。
(a%b)%c = R%c
一方、a÷b = Q…R ⇔ a = bQ+R = kcQ+R より
a%c = (kcQ+R)%c = R%c ∵ ②
以上より(a%b)%c = a%c = R%c [完]
▲閉じる
証明では触れませんでしたが、
aをbで割った商をQb, cで割った商をQcとすればQb = Qc%k となって奥が深いです。
ポイント
b=kcと表現するのはいいとして、商を定義して生真面目に商の形を求めようとすると⓪を含めとんでもない記述量になったので割愛しました。②を使うことで商を考えずに済んだのが大きいです。完璧主義だとこれに気づけないかも知れません。

⑩ (c-b)%c=(c-1)-(b-1)%c (1≦b＜c)

割られる数に割る数が含まれている場合も、この条件下では分離する事ができます。

割られる数をb-1, 割る数をcとします。
商をQ, 余りをRとします。
b-1=cQ+R
∴ c-(b-1) = c-(cQ+R) = -cQ+(c-R)
∴ c-b+cQ = 0c+{(c-1)-R}
⇔ (c-b+cQ)÷c = 0…(c-1)-R ※0≦(c-1)-R＜c
∴ (c-b+cQ)%c = (c-1)-R
左辺に②を適用, 右辺にR=(b-1)%cを代入
(c-b)%c = (c-1)-(b-1)%c [完]
▲閉じる

ポイント
意識した点は2つです。
1つ目は、％演算の中にマイナスを残したくなかったので、マイナスが着いているbを主人公にした事です。
2つ目は、最初はb=cQ+Rで定義していたのですが余りの範囲が0≦c-R＜c-1となったため、その調整としてb-1=cQ+Rで定義し直したところから書き始めています。調整の対象がbなのはcでは上手くいかないからです。

// QUEST_/

現在苦戦している未解決問題がこちら

1. a%(b+c)のbとcを分離せよ！

2. (a%b)%cを一般化せよ！

3. [[a/b]/c]=[a/bc]を簡潔に示せ！

4. 実数へ拡張せよ！

以上4つになります。解決できる保証はありませんが楽しみにしててください