剰余の問題について

基本情報技術者試験の問題にて、

pを2以上の整数とする。任意の整数nに対して、
n=kp+m (0 <= m < p)
を満たす整数kとmが一意に存在する。このmをnのpによる剰余といい、
n mod pで表す。（-10000）mod 32768に等しくなるものはどれか。

ア -(10000 mod 32768)
イ (-22768)mod 32768
ウ 10000 mod 32768
エ 22768 mod 32768

という問題があります。

この問題の解答は「エ」となるのですが、
解き方がどうしても理解することができません。

解説では

（-10000）mod 32768と等しいのは
32768+(-10000)=22768から
22768mod32768となる。

と書いてあるのですが、このように解答していく
プロセスがさっぱり見えてきません。

この解法の仕方をレクチャーしていただけないでしょうか。

No.2 ベストアンサー 回答者： noname#160244 回答日時： 2007/09/17 02:43

その「解説」の解説にはなっていませんが・・・

剰余の演算はアナログ時計のようなものです。

普通は1～12の数字が書いてありますが、この問題の場合、1～32768の数字が書いてあるアナログ時計をイメージします。
そしてこの時計で、nのぶんだけ針をまわします。nが正の場合は時計回りに、負の場合は反時計回りにまわします。

n = -10000なので、時計の0の位置（＝32768の位置）から反時計回りに針を10000まわします。
すると針は22768を指します。
つまり、(-10000) mod 32768 = 22768です。

アは時計回りに針を10000だけまわすので、針の位置は10000。それにマイナスが付いているので
　-(10000 mod 32768) = -10000

イは反時計回りに針を22768だけまわすので、針の位置は10000。
　つまり (-22768) mod 32768 = 10000

ウは時計回りに針を10000まわすので、針の位置は10000。
　よって 10000 mod 32768 = 10000

エは時計回りに針を22768まわすので、針の位置は22768。
　よって 22768 mod 32768 = 22768

というわけで(-10000) mod 32768に等しいのはエです。


なお、時計で説明しましたが、剰余は割り算をしたときの余りのことです。
k は n / p の商。
n mod p は n / pの余り。

この回答へのお礼

すごいイメージが取りやすい解法です＾＾
アナログ時計のイメージだと、簡単に解けた感じがします。
ありがとうございます！！

お礼日時：2007/09/17 12:26

No.1 回答者： ymmasayan 回答日時： 2007/09/17 00:54

難しく考えない方がいいです。

ｋを動かしてみると
ｋ＝１　　ｍ＝－４２７６８
ｋ＝０　　ｍ＝－１００００
ｋ＝－１　ｍ＝　２２７６８

(0 <= m < p)の条件式から　k=-1　が決まります。
するとｍは解説のような式になります。

この回答へのお礼

理解できました。
感謝感激です＾＾

お礼日時：2007/09/17 12:35