2進数において、３の倍数になる規則は？

質問

１０進数では全ての桁の和が３の倍数になればいい
では２進数において３の倍数になる規則はなんでしょうか。

逆に３進数において２の倍数になる規則はなんでしょうか。
後者は１の個数が偶数。
でいいですか？

前者についてはなかなか手法がみつかりません。。

回答No.4

ranx · ベストアンサー

No.2です。

> 10^1 ≡ 10 ≡ -1 (mod 11)
> の式に現れる数は全て２進表記ですよね？

その通りです。

> 10^2 ≡ (10)^2 ≡100(4のこと)≡ 1（４を３で割るとあまりは１）　 (mod 11)
> と考えていいですか？

その通りです。

お礼

ありがとうございます。
これなら後々も応用できそうです！
またよろしくおねがいします＾＾

回答No.5

noname#6587

フーン、初めて聞きました。知らなかった。
即席に考えた私の答え、、、
（既に回答している皆さんと同じことですが、、、、）

「１０進数では全ての桁の和が３の倍数になればい」
－－－＞　
　　数字の並びが　ＡＢＣの10進数は
　　　　(3*3+1)*(3*3+1)*A + (3*3+1)*B + C
一目瞭然。

「では２進数において３の倍数になる規則はなんでしょうか。」
－－－＞
(同様の発想から云うと）
　　数字の並びが　ＡＢＣの2進数は
　　　　(3-1)*(3-1)*A + (3-1)*B + C
だから、A-B+C が　0 (か　3 の倍数?)。
　（この場合は、０１１->3か110->6。）

　　ＡＢＣＤについては、
(3-1)*(3*3-2*3+1)*A + (3-1)*(3-1)*B + (3-1)*C + D
を見ると、-A+B-C+D が　0 (か　3 の倍数?)。
0011->3
0110->6
1001->9
1100->12
1111->15
（「・・か　3 の倍数」　が出てこないですね。）
もっと長くても、見通せますね。

「逆に３進数において２の倍数になる規則はなんでしょうか。 」
－－＞
　　　(2+1)*(2+1)*(2+1)*A + (2+1)*(2+1)*B + (2+1)*C + D
だから、
A+B+C+D が　( 0 か ) 2の倍数。
検証は自分でやってみて！

お礼

ありがとうございます。
私も初めてでした。
またよろしくおねがいします

回答No.3

massie

結局＃１さん、＃２さんと同じことかもしれませんが・・・。
　　　　　　　　　３で割ったときのあまり
　１桁目＝１・・・　　　　　１
　２桁目＝２・・・　　　　　２
　３桁目＝４・・・　　　　　１
　４桁目＝８・・・　　　　　２
　５桁目＝１６・・・　　　　１
という具合に奇数桁は３で割るとあまりが「１」偶数桁はあまりが「２」ということです。ということは奇数桁に数字（２進数ですからもちろん「１」）がある場合は「１」、偶数桁に数字がある場合は「２」をたしていき、その合計が３で割り切れるときは３の倍数というのはどうでしょうか。
　１００１００１００１１１１０１０１１１
奇数桁＝７
偶数桁＝４　　２×４＝８
　７＋８＝１５　なので３の倍数

お礼

ありがとうございます。
なんとかわかってきました＾＾
またよろしくお願いします

回答No.2

ranx

> １０進数では全ての桁の和が３の倍数になればいい
と機械的に覚えていたのでは応用がききません。
なぜそうなのかを理解しておきましょう。
10^1≡1 (mod 3) であることが重要です。このため、
10^2≡1^2≡1 (mod 3)
一般に10^n≡1^n≡1 (mod 3) となるため、
a0 + a1・10 + a2・10^2 ・・・ + an・10^n ≡ a0 + a1 + a2 + ・・・ + an
となるのです。

2進数では
10^1 ≡ 10 ≡ -1 (mod 11)
10^2 ≡ (-1)^2 ≡ 1 (mod 11)
一般に 10^n=10^(n-2)・10^2 ≡ 10^(n-2) (mod 11)ですから、
一桁おきに足し算と引き算を入れ換えるNo.1さんの方法で正解です。

3進数では
10^1 ≡ 1 (mod 2) ですので、10進数の場合の3の倍数と同じようになります。
つまり、各桁の数をすべて足し合わせた合計が2の倍数なら元の数も2の倍数です。

お礼

ありがとうございます。
確認のためなんですが、modや２進表記に慣れていないので以下の点だけ質問させてください。
10^1 ≡ 10 ≡ -1 (mod 11)
の式に現れる数は全て２進表記ですよね？
かなり無意味なことですが、
10^2 ≡ (10)^2 ≡100(4のこと)≡ 1（４を３で割るとあまりは１）　 (mod 11)

と考えていいですか？

回答No.1

noname#6248

とっさに思いついたのであまり自信はありませんが…
例
1001010101010101010101011101101の場合
-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
+の合計と-の合計を足し算します。
『その結果が３の倍数ならば３の倍数である』とは言えないですかね？
＋＝１３
－＝４
１３－４＝９→３の倍数→1001010101010101010101011101101は三の倍数。

二進数→１，２，４，８，１６，３２，６４，１２８，２５６…ですよね？
最寄の３の倍数を考えると
１→０
２→３
４→３
８→９
１６→１５
３２→３３
６４→６３
１２８→１２９
２５６→２５５
■→□
■と□を見ていくと、１減っている、１増えているが順になっているようです。
■の部分の上下を比べると２倍しているわけですから…
１の時＝１少なければ３の倍数ですね。
・１少なければ３の倍数を２倍する→２少なければ３の倍数→１多ければ３の倍数
・１多ければ３の倍数を２倍する→２多ければ３の倍数→１少なければ３の倍数
どうやら交互に出ているようです。数学的帰納法を簡素化したもの。

１少なければ３の倍数＋１多ければ３の倍数＝３の倍数
１少なければ３の倍数×３＝３の倍数
１多ければば３の倍数×３＝３の倍数

ですかね…
証明はしませんがおそらく正解かと思います。

お礼

なるほど、ありがとうございます

１０進数のように一筋縄ではいかないわけですね・・・
頭が混乱しているのでまたあとでじっくり読み返したいと思います。