人気サイト様 最新記事

博士ちゃんねる ヘッドライン

レスの強調ウゼェー!というドクターへ

レス内の強調表示をOFFにする コチラをクリックして切り替えてください。設定は30日間Cookieに保存されます。
現在のステータス:強調有効

何で割れる数かの判定を考えるスレ @ [数学板]


何で割れる数かの判定を考えるスレ @ [数学板]
1: 132人目の素数さん 2016/03/31(木) 10:40:24.88 ID:17pF/omr.net
2: 下一桁が偶数
3: 全部の位を足した数が3で割れる
4: 下2桁が4で割れる
5: 下一桁が0か5
6: 2の条件と3の条件の複合
7:
8: 下3桁が8で割れる
9: 全部の位の和が9で割れる
10: 下一桁が0
11: 下2桁の差が1で最大桁が1

7とそれ以外を考えよう
2: 132人目の素数さん 2016/03/31(木) 10:48:18.85 ID:+gr4vIpu.net
11がおかしいことが分からなかったのか
3: 132人目の素数さん 2016/03/31(木) 11:01:06.64 ID:17pF/omr.net
すまない11追記
もしくは1桁ごとの和が11か、桁飛ばしの和同士の差が11か0か
4: 132人目の素数さん 2016/03/31(木) 11:45:30.30 ID:DyzSSAQn.net
(1桁目) + (2桁目*3) + (3桁目*2) + (4桁目*6) + (5桁目*4) + (6桁目*5) + (7桁目)+...以下ループ
7の倍数の時が7で割れる条件だけど、綺麗な方法はあるのかね一般に素数でわれる時の条件ってあるのかな
7: 132人目の素数さん 2016/03/31(木) 12:02:39.16 ID:17pF/omr.net
>>4
3桁ごとに区切ってグループを一つ飛ばしに和にする→その差が7で割れるかどうかが判定だが3桁までは違う方法になる
5: 132人目の素数さん 2016/03/31(木) 11:45:34.89 ID:17pF/omr.net
7って4桁以上なら判定方法あるけど、3桁ってあるかな?
6: 132人目の素数さん 2016/03/31(木) 11:55:11.97 ID:JQ6/GkHF.net
3桁なら普通に割り算すればよくね
8: 132人目の素数さん 2016/03/31(木) 12:14:52.76 ID:17pF/omr.net
>>6
やっぱりそうなるのかね
9: 132人目の素数さん 2016/03/31(木) 12:26:11.16 ID:uY7ZNBsc.net
1だが帰宅。PCから
12: 3の判定と4の判定の複合
13:
10: 132人目の素数さん 2016/04/01(金) 08:46:16.91 ID:JoQB8dE+.net
実際に割ってみるよりも簡単でなければ判定法として意味がないだろうが、これを言うと、「簡単」を定義しろって怒られるよな。
12: 132人目の素数さん 2016/04/01(金) 17:53:32.32 ID:LyhNKHnd.net
>>10
そうだな。ムズいなこのスレ
でもそこまで深く考えなくて3桁~10桁までが通用すると思われるものあったら挙げて皆で検討しようってスレにしよう!
11: 132人目の素数さん 2016/04/01(金) 17:06:31.24 ID:I9/rgeRm.net
計算時間が短くて済む、とかならまだ定義しようがあるかな
13: 132人目の素数さん 2016/04/02(土) 04:46:15.05 ID:azzL1IGB.net
100a+10b+c≡2a+10b+c (mod7)で
14: 132人目の素数さん 2016/04/02(土) 08:44:42.95 ID:09RqBd/V.net
>>13
要は、7(2a+10b+c)ってことか。
3桁は対応してるが、10桁は対応してないと思うかな。
10桁になると、abcの値が出しにくいか10^9a+...+jだよな
そうなると行列の桁要素を抽出とかして対応出来ないかな?
15: 132人目の素数さん 2016/04/02(土) 08:51:01.60 ID:09RqBd/V.net
1001っていうのが7*11*13になってて、13の倍数の場合1001を抽出できれば対応できるものって言う風になる
16: 132人目の素数さん 2016/04/02(土) 08:53:53.49 ID:09RqBd/V.net
だから1001から7が抽出できるから7の倍数にも対応していたが、4桁以下は7(2a+10b+c)を使うのが無難そうだな
17: 132人目の素数さん 2016/04/03(日) 12:37:57.84 ID:7+GIbJDI.net
7の倍数判定

以下、7を法として
10≡3 より 10^(3+6k)≡-1, 10^(6+6k)≡1
(kは非負整数)

A=(a_n)*10^(3n)+…+(a_3)*10^9+(a_2)*10^6+(a_1)*10^3
とおけば

(Aが7の倍数)
⇔(A≡0)
⇔((-(a_1))+(a_2)+(-(a_3))+…+(a_n)(-1)^n≡0)
⇔(Aを下から3桁ずつに区切って…)
19: 132人目の素数さん 2016/04/03(日) 13:02:06.18 ID:7+GIbJDI.net
>>17追記

A=(α_n)*10^(6n)+…+(α_3)*10^18+(α_2)*10^12+(α_1)*10^6
とおけば
(Aが7の倍数)
⇔(∑[t=1, n](α_t)≡0)
⇔(Aを6桁ずつに区切ったとき、それらの総和が7の倍数)
21: 132人目の素数さん 2016/04/03(日) 13:25:57.07 ID:7+GIbJDI.net
>>17,19訂正

それぞれ (a_0)*10^0, (α_0)*10^0 の項を忘れていた

あと各レスの最後の行は同値ではない
例えば、
A=1234569のときに、
(a_2)=0, (a_1)=1233, (a_0)=1569

(α_1)=2, (α_0)=-765431
とおいてもよい
26: 132人目の素数さん 2016/04/03(日) 15:23:18.52 ID:ie3Vh7Ur.net
>>17
かなり有効な手だな
俺の3桁法よりずっと数学的だ
難点は単純かどうかって所?
30: 132人目の素数さん 2016/04/08(金) 22:57:32.53 ID:eIW+dqEy.net
A 分割して一気に和差をとる方法>>17,20,28)
B 徐々に桁数を削っていく方法>>23,29)
の2種類の一般化できる方法がある

Aは調べる数が小さすぎると使えないが、Bは調べる数が大きすぎると計算が面倒になる
31: 132人目の素数さん 2016/04/08(金) 23:56:00.13 ID:POuZoymv.net
Bを繰り返し使えばAになるので、2つの方法を区別する意味はあまり無いような
管理人より:「Xを法として…」というのは「Xで割ったあまりを求める」という意味。「10」を法とした場合、32は「2(mod 10)」と表現されます。イメージとしては0~X-1までの数直線をくるっと丸めて0のところにひっつける形に。詳細はこちら→法とモジュロ:サルにも分かるRSA暗号
18: 132人目の素数さん 2016/04/03(日) 12:46:30.77 ID:7+GIbJDI.net
11の倍数判定
10^(1+2k)≡-1, 10^(2+2k)≡1 (mod 11)
を利用

13の倍数判定
10^(3+6k)≡-1, 10^(6+6k)≡1 (mod 13)
を利用
20: 132人目の素数さん 2016/04/03(日) 13:15:58.65 ID:7+GIbJDI.net
任意の奇素数pについて、10とpは互いに素だから、オイラーの定理より
10^φ(p)=10^(p-1)≡1 (mod p)

よって、
「Aを下から(p-1)桁ずつに区切ったときにそれらの総和がpの倍数なら、Aもpの倍数」
22: 132人目の素数さん 2016/04/03(日) 13:30:06.51 ID:7+GIbJDI.net
>>20訂正
p≠5

以上
23: 132人目の素数さん 2016/04/03(日) 14:35:15.48 ID:2ItAYAJi.net
a[n]…a[1]a[0] = Σa[i]*10^i


a[n]…a[0] が7の倍数 ⇔ a[n]…a[1] - 2*a[0] が7の倍数
2*a[n]…a[0] + (a[n]…a[1] -2*a[0]) = Σ21*a[i+1]*10^i ≡ 0 (mod 7)


a[n]…a[0] が13の倍数 ⇔ a[n]…a[1] + 4*a[0] が13の倍数
4*a[n]…a[0] - (a[n]…a[1] + 4*a[0) = Σ39*a[i+1]*10^i ≡ 0 (mod 13)


a[n]…a[0] が17の倍数 ⇔ a[n]…a[1] - 5*a[0] が17の倍数
5*a[n]…a[0] + (a[n]…a[1] -5*a[0]) = Σ51*a[i+1]*10^i ≡ 0 (mod 17)


a[n]…a[0] が19の倍数 ⇔ a[n]…a[1] + 2*a[0] が19の倍数
2*a[n]…a[0] - (a[n]…a[1] +2*a[0]) = Σ19*a[i+1]*10^i ≡ 0 (mod 19)
25: 132人目の素数さん 2016/04/03(日) 14:54:00.26 ID:2ItAYAJi.net

14539が7の倍数 ⇔ 1453-2*9=1435が7の倍数 ⇔ 143-2*5=133が7の倍数 ⇔ 13-2*3=7が7の倍数…OK
27: 132人目の素数さん 2016/04/03(日) 15:25:51.79 ID:ie3Vh7Ur.net
>>23
俺の3桁のと同じだがMod7とMod19が同じ方法というのが良い点だな
けっこう使える場面多そう
28: 132人目の素数さん 2016/04/04(月) 02:56:19.40 ID:yYQc9xiS.net
実用性があるかどうかはともかく、ある素数pで割り切れるかどうかの判定に、k桁ごとに区切って、奇数番目のみの和と、偶数番目のみの和を求め、さらにそれらの差をとってそれがpで割り切れるかどうかを見ればよい、という方法が存在するのは、pが10^k+1の約数となるようなケースだが、そのようなkが存在する条件は、1/pを循環小数で表したときの循環節が偶数となることと同値で、素数全体の中でその条件を満たすものの割合(厳密に言うとある数以下の素数の中での割合の極限)はちょうど2/3らしい。

◯:7,11,13,17,19,23,29,47,59,61,73,89,97,…
×:3,31,37,41,43,53,67,71,79,83,…
29: 132人目の素数さん 2016/04/07(木) 15:13:32.01 ID:b3dVU0Ji.net
1000m+nが17(または59)の倍数⇔n-3mが17(または59)の倍数
1000m+nが19(または53)の倍数⇔n-7mが19(または53)の倍数
1000m+nが23(または29)の倍数⇔2n-mが23(または29)の倍数
1000m+nが31の倍数⇔8m+nが31の倍数
1000m+nが37の倍数⇔m+nが37の倍数
100000m+nが41の倍数⇔m+nが41の倍数
39: 132人目の素数さん 2016/04/15(金) 00:41:22.80 ID:f0QN65F0.net
3桁の数で37の倍数となるのは
・777のように全ての桁が同じ数字
・数字を巡回置換すると037,074,148,185,259,296のどれかに一致する
(例えば592は右に1桁ずらして巡回させると259に一致)のいずれかの場合のみ。

これを覚えるのが面倒なら、
592-222=370
というように全ての桁が同じ数を引いてどれかの桁が0になるようにし、これを巡回置換したときに037か074になるかどうかを見ればよい。
4桁以上の場合は>>29
32: 132人目の素数さん 2016/04/08(金) 23:57:36.48 ID:POuZoymv.net
301=7*43
799=17*47

を使って7,17,43,47の倍数判定法も作れる
33: 132人目の素数さん 2016/04/09(土) 01:00:51.86 ID:cOPMPQb5.net
11で割った余りを求める方法。
慣れればかなり素早く暗算できるようになる。

例:290563
これを2,9,0,5,6,3という数列と見る
2,9を9-2つまり7に置き換える
7,0,5,6,3になる
以下同様に
-7,5,6,3
12,6,3
大きい数が出てきたら11を加えたり引いたりしてよい
1,6,3
5,3
-2

最後に残った数が11で割った余り(11を加えれば9になる)
40: 132人目の素数さん 2016/04/15(金) 00:50:01.46 ID:f0QN65F0.net
ちなみに3桁で37の倍数であるような数は、3桁のうち任意の2つの数字の差は0,3,4,7のどれかなので、2桁だけ見てその差が1,2,5,6,8,9のどれかであれば、残りの桁を見るまでもなく37の倍数ではないと分かる。
34: 132人目の素数さん 2016/04/09(土) 01:04:08.61 ID:cOPMPQb5.net
7,0,5,6,3のように0がある場合、段階をすっとばして
12,6,3
といきなりやってもいい。
つまり0は+の記号と見なしてしまえる。
35: 132人目の素数さん 2016/04/09(土) 09:28:43.56 ID:GN+OXE90.net
>>33
普通の割り算じゃん
37: 132人目の素数さん 2016/04/09(土) 09:52:40.39 ID:cOPMPQb5.net
>>35
そう言ってしまえばそれまでだけどね。
十進位取り記数法を少し拡張して、0~9の範囲を超えて10以上や-1以下の数字を許容している。
これによって商となる数字に自由度が持たせられるので、通常の割り算と比べて若干楽になる。
11で割る場合は、何も考えずに頭の数字をそのまま商とすればいいことになる。
36: 132人目の素数さん 2016/04/09(土) 09:35:19.32 ID:NDNx33ox.net
グレブナー基底を使ったアルゴリズムの話とかじゃないスレッド
小手先感が強い
38: 132人目の素数さん 2016/04/14(木) 17:07:01.43 ID:Ih1l1Ust.net
計算機を使うなら倍数判定にアルゴリズムの工夫なんていらんでしょ
暗算や手計算のための小手先の方法こそ、このスレの趣旨
46: 132人目の素数さん 2016/04/19(火) 00:07:54.70 ID:xEZIpvG0.net
>>36
>>38
いいことを言った
数学的な要因はあるが「結果こんな簡単な倍数判定法があるんよ」って教え合うスレ
41: 132人目の素数さん 2016/04/17(日) 00:02:19.51 ID:tjJgZPIe.net
n=ax^2-by^2の形で表せる整数の素因数をpとすると
・pはx,yの公約数
・abはmod pで平方剰余

のいずれかが成り立つ。

例えば、x,yが互いに素とすると
n=x^2+y^2⇒p≡1(mod 4)
n=x^2-2y^2⇒p≡1,7(mod 8)
n=x^2+2y^2⇒p≡1,3(mod 8)
n=x^2-3y^2⇒p≡1,11(mod 12)
n=x^2+3y^2⇒p≡1(mod 6)
n=x^2-5y^2⇒p≡1,4(mod 5)
n=x^2+5y^2⇒p≡1,3,7,9(mod 20)
n=x^2-6y^2⇒p≡1,5,19,23(mod 24)
n=x^2+6y^2⇒p≡1,5,7,11(mod 24)
42: 132人目の素数さん 2016/04/17(日) 00:06:39.08 ID:tjJgZPIe.net
>>41
誤)例えば、x,yが互いに素とすると
正)例えば、x,yが互いに素でかつpはabの約数でないとすると
43: 132人目の素数さん 2016/04/17(日) 23:57:53.35 ID:tjJgZPIe.net
>>41,42
p=2の場合を考慮していなかったので、さらに訂正。

誤)例えば、x,yが互いに素とすると
誤)例えば、x,yが互いに素でかつpはabの約数でないとすると
正)例えば、x,yが互いに素でかつpはabの約数でなくかつ奇素数とすると
44: 132人目の素数さん 2016/04/18(月) 00:01:06.49 ID:8z+MpyTr.net
「例えば、pは2abxyの約数でないとすると」
と書いたほうが簡潔だったかな。
47: 132人目の素数さん 2016/04/19(火) 04:32:03.47 ID:qtBs+Q6v.net
>>41の根拠を書いてなかったけど、平方剰余の相互法則から導かれる。
詳しく書くと長いので証明は割愛。ググれ。
管理人より:「aとbが互いに素」というのは、「aとbが1以外に共通する約数を持たない」という意味です。
48: 132人目の素数さん 2016/10/07(金) 22:03:52.46 ID:Q3TTl0VX.net
良スレ
45: 132人目の素数さん 2016/04/19(火) 00:05:31.66 ID:xEZIpvG0.net
俺が居ない間にこのスレここまで来たか
俺がついていけん

長らく更新をおやすみしてましたが、また更新再開です。はあぁ…もう日本ありがたい。
今回もまた仕事でベトナムに行ってきて、体調を崩すこともなく好調ですが、1週間の海外出張はさすがに長い。物珍しさがあるのは最初の3日くらいですなぁ。
向こうで、夜のお月さまを見ながら「天の原 ふりさけみれば 春日なる…」の例の和歌を思い出していましたが、昔の防人たちもそんな心境だったかもしれない。

向こうでやってたことといっても、たがいの技術者がワガママ言うのを「まぁまぁ!気持ちはわかるけど今回はこのへんで妥協してくださいよ!」というのを各方面に対して調整してまわるという、誰もやりたがらない仕事。
調整の結果をホワイトボードに大量の図を書いて説明したのですが、あれで伝わったかどうかいまひとつ自信がないですよ。
向こうの技術者の英語も発音がふわあーっとしててよくわからず、ノートPCやスマホで綴りを書いて筆談する始末。ナンテコッタ、めんどくさい。
しかし、「伝えたい」という強い意志があれば、なんとかなるものです。

ベトナムレポートについては前回行ったときに長々と書きましたので、あちらの事情に興味のある方はどうぞ。
というわけで、なかなかの良スレかと思いましたが、残念ながら数学板はもれなく大量の荒らしが入るので、この後はスレが機能せずおしいことに。
管理人も中学生のころに、「○で割れるかどうか」の簡単な説明を先生に教えてもらって役にたったことがあります。
よく知られてる「全部の桁を足した数が3で割れたら、その数も3で割れる」みたいなやつ以外のものを探そうじゃないか!という初心者向けのスレ。

…という意図で»1さんはスレを立てたものと思いますが、後半はやたらと難しく読むのも困難なスレとなりました。さすが数学板ェ…('A`)
わりかし、7、11、13あたりで割り切れるかどうか、という点はパッと見てよくわからず、簡単な方法が捻出されれば大変有効ではあるんですが、簡単な方法というのは難しそうですね。

* * *

巻末欄が寂しいから、以下ちょっとした豆知識のコーナー。
「37」は素数ですが、「111」「222」「333」「444」「555」「666」「777」「888」「999」の約数。

「1」が連続した数を二乗すると以下のように回文みたいになります。
11^2 = 121
1+2+1 = 4 = 2^2

111^2 = 12321
1+2+3+2+1 = 9 = 3^2

1111^2 = 1234321
1+2+3+4+3+2+1 = 16 = 4^2
桁が大きくなっても規則性は健在。
11111111111111^2 = 123456790123454320987654321
1+2+3+4+5+6+7+9+0+1+2+3+4+5+4+3+2+0+9+8+7+6+5+4+3+2+1 = 106
106 = 5^2 + 9^2

111111111111111^2 = 12345679012345654320987654321
1+2+3+4+5+6+7+9+0+1+2+3+4+5+6+5+4+3+2+0+9+8+7+6+5+4+3+2+1 = 117
117 = 6^2 + 9^2

1111111111111111^2 = 1234567901234567654320987654321
1+2+3+4+5+6+7+9+0+1+2+3+4+5+6+7+6+5+4+3+2+0+9+8+7+6+5+4+3+2+1 = 130
130 = 3^2 + 11^2 = 7^2 + 9^2

こんなやつも。
3 * 37 = 111
33 * 3367 = 111111
333 * 333667 = 111111111
3333 * 33336667 = 111111111111
33333 * 3333366667 = 111111111111111
333333 * 333333666667 = 111111111111111111

こんなやつも。
(0 * 9) + 1 = 1
(1 * 9) + 2 = 11
(12 * 9) + 3 = 111
(123 * 9) + 4 = 1111
(1234 * 9) + 5 = 11111
(12345 * 9) + 6 = 111111
(123456 * 9) + 7 = 1111111
(1234567 * 9) + 8 = 11111111
(12345678 * 9) + 9 = 111111111
(123456789 * 9) + 10 = 1111111111
(1234567900 * 9) + 11 = 11111111111
(12345679011 * 9) + 12 = 111111111111
こゆの誰が見つけるのかな?

ガードナーの数学パズル・ゲーム (完全版 マーティン・ガードナー数学ゲーム全集1)
マーティン・ガードナー
日本評論社
売り上げランキング: 293,383



人気サイト様 最新記事

博士ちゃんねる ヘッドライン

    • ※1 : ドクター・ノオ・ネーム
    • 2018.9.18 0:53
    受験生の頃はこういうのをつかって計算ミスを検出する方法を考えたな。131*56だったらかけた結果を3で割ったあまりは(1(+3)+1)*(5(+6))=1とすぐわかるからそれで確認する、みたいに。
    • ※2 : ドクター・ノオ・ネーム
    • 2018.9.18 18:02
    今までの数学を、おせーてる奴らで(~しよう)とかて言ってくる人は皆無
    奴らが言うのは、(~せよ)とか、(~とした時)とか、大体頭から決めつけやがるからね
    • ※3 : ドクター・ノオ・ネーム
    • 2018.9.19 14:28
    数学はからっきしなので一つ一つ理解するのに大変時間がかかったが、数の織りなす規則正しさには何とも美しさを感じるものだな…
    • ※4 : ドクター・ノオ・ネーム
    • 2018.9.20 3:11
    リーマンさん出番ですよ。
  1. トラックバックはまだありません。


コメ欄での議論はおおいにけっこうですが、当サイトではドクター同士の罵り合いは禁止となっております。反論する際には、相手の意見・人格を尊重し、どうぞ冷静に。