星塚研究所

数学を主とした形式科学,自然科学,大学・大学院に関する2chと5chのまとめサイト

何で割れる数かの判定方法を考えるスレ

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)
*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つの方法を区別する意味はあまり無いような

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の根拠を書いてなかったけど、平方剰余の相互法則から導かれる。
詳しく書くと長いので証明は割愛。ググれ。

48: 132人目の素数さん 2016/10/07(金) 22:03:52.46 id:Q3TTl0VX.net
良スレ
45: 132人目の素数さん 2016/04/19(火) 00:05:31.66 id:xEZIpvG0.net
俺が居ない間にこのスレここまで来たか
俺がついていけん


参考文献

http://ai.2ch.sc/test/read.cgi/math/1459388424/

*1:-(a_1