請問有人知道17跟19的倍數怎麼判別嗎??

[nitzschia (妮琪亞)]

我們都很熟3~13的倍數判別法

例如3的倍數是加起來值為3的倍數
    5的倍數尾數是0或5
有些是用數學歸納法可以證明出來的

那17跟19有方法判別嗎??
or哪裡可以查相關的資訊呢??

先謝謝大家嚕


--
※ 發信站: 批踢踢實業坊(ptt.csie.ntu.edu.tw)
◆ From: 61.230.9.229
→ hopeless:拿計算機除除看^^"" (確定有啦我也忘了)
> -------------------------------------------------------------------------- <

作者: firebug (休息是振作的前提) 站內: tutor
標題: Re: 請問有人知道17跟19的倍數怎麼判別嗎??
時間: Wed Jan  8 16:04:38 2003

直接用除的
如果你是教家教的話

我連11的倍數都不太教學生
因為雖然可以學
但是太不實用了
與其要花很多時間去記公式
還不如用除的比較快
也可以讓學生把腦容量留下來裝一些三角函數 ^^"

--
※ 發信站: 批踢踢實業坊(ptt.csie.ntu.edu.tw)
◆ From: 140.112.7.59

> -------------------------------------------------------------------------- <

作者: bbbing (逼偪冰) 看板: tutor
標題: Re: 請問有人知道17跟19的倍數怎麼判別嗎??
時間: Wed Jan  8 16:58:41 2003

證明起來倒不用那麼復雜...

像1/7=0.142857.....
取142857*7=999999

例:abcdefghijklm(請當作是13位數)

那就可以分解成:a*10^13+bcdefg*10^7+hijklm

(請慢慢看...) =a*10^6*(999999+1)+bcdefg*(999999+1)+hijklm

              =(a+bcdefg+hijklm)+999999(a*10^6+bcdefg)

因為999999為7的倍數，所以後半捨去後(必整除)...
前半就形成六個六個一組的情形了...

所以像1/13=0.076923........
將76923*13=999999
接著同理...
--
11之會有單數位減偶數位是因為1001、100001、10000001...
也是11的倍數，才會推導出來...

--
※ 發信站: 批踢踢實業坊(ptt.csie.ntu.edu.tw)
◆ From: 140.112.50.185

> -------------------------------------------------------------------------- <

作者: TwoOneboy (好樣的 ^^) 看板: tutor
標題: Re: 請問有人知道17跟19的倍數怎麼判別嗎??
時間: Wed Jan  8 16:15:56 2003

有個簡易方法可以判別唷
3的倍數：1/3循環節是1，所以把各個數字加起來看是不是3的倍數即可
7的倍數：1/7循環節是6，所以把每6位加起來看是不是7的倍數，或者是可以把
         每6/2=3位交錯相減，看看是不是7的倍數
9的倍數：1/9循環節是1，所以把各個數字加起來看是不是9的倍數即可
11的倍數：1/11循環節是2，所以把每2位加起來看是不是11的倍數，或者可以每2/2=1
          位交錯相減看看是不是11的倍數
同理，1/17循環節是16，所以把每16位加起來看是不是17的倍數，或者可以每16/2=8
位交互相減看看是不是17的倍數
1/19循環節是18，接下來應該不用我講囉

這個方法限用於質數，至於證明，因為我不是數學系的，所以不管它 ^^""
應該是不會太難證吧我想，先證明循環節一定是啥的因數
然後就留給不用考期末考的人想了  ^^""

實用上，若質數很大，這個方法可能還是很難用，所以還有另一種方法
以17為例：
17 X 3 = 51
所以我們可以做這樣子的運算--把那個數減去尾數的51倍，再除以10
                            也可以一次取末2位、末3位等等，若原數是17的倍數
                            經此運算後，一定也還是17的倍數，以下舉一個實例

9432712718
      90
-----------------
94327037
  185
-----------------
94142
210
-----------------
731
 5
-----------------
68

因為17|68，所以該數是17的倍數！

至於19的話，因為19 X 9 = 171
所以就要扣掉尾數的17倍

--
※ 發信站: 批踢踢實業坊(ptt.csie.ntu.edu.tw)
◆ From: 140.112.212.119
→ timmy:循環結怎麼定阿?
→ hopeless:數學系的吧
→ DEREK:其實是醫學系的
→ TwoOneboy:更正：循環節-->最小循環節長度......
→ TwoOneboy:最小循環節只能用除的，至於循環節我忘了
→ chau:質數p的循環節位數一定是p-1的因數
> -------------------------------------------------------------------------- <

作者: TwoOneboy (好樣的 ^^) 看板: tutor
標題: Re: 請問有人知道17跟19的倍數怎麼判別嗎??
時間: Wed Jan  8 17:50:27 2003

想到囉～
因為n是質數，如果m不整除n，則m/n餘數最多只有(n-1)個
因此可以用鴿籠原理證明1/n一定循環且循環節長度最多是(n-1)位

接下來證明(n-1)一定是最小循環節長度的倍數
（或者說每隔(n-1)位數字一定相同）

設1/n = (10^-q) X (0.a1a2a3...an....)，a1不等於0
易證(10^q) X (1/n) X (10^(n-1)-1）是個整數
所以a1=an，a2=a(n+1)，依此類推

所以每隔(n-1)位數字一定相同

--
※ 發信站: 批踢踢實業坊(ptt.csie.ntu.edu.tw)
◆ From: 140.112.212.119

> -------------------------------------------------------------------------- <

作者: doa2 (碼的死DB) 看板: tutor
標題: Re: 請問有人知道17跟19的倍數怎麼判別嗎??
時間: Wed Jan  8 18:06:59 2003

when p為質數  n^p同餘n (mod p)

此為Fermat定理

1.when p|n時  顯然成立

2.when p不整除n時

考慮n,2n,3n,....(p-1)n

他們都與p互質  又0n,n,2n...(p-1)n為模p的一個完系

所以n,2n,3n...(p-1)n互不同餘(關於模p)

故n˙2n˙3n..(p-1)n同餘1˙2˙3˙....(p-1)

兩邊消去(p-1)!  則得到n^(p-1)同餘1(mod p)


證明了定理之後我們取n=10

則得10^(p-1)同餘1(mod p)  (p=2,5除外)

也就是p|9999...9   (p-1個9)

故每p-1位就循環一次

--
※ 發信站: 批踢踢實業坊(ptt.csie.ntu.edu.tw)
◆ From: 140.112.249.46
→ TwoOneboy:就是這樣沒錯！ 這題以前是基本題說....XD
→ doa2:其實想了一下還是想起來啦
→ doa2:對了 我沒證為什麼是完系 大家自己證吧 不難
> -------------------------------------------------------------------------- <

作者: doa2 (惱人的投資學報告) 看板: tutor
標題: Re: 請問有人知道17跟19的倍數怎麼判別嗎??
時間: Thu Jan  9 11:31:34 2003

if (a,n)=1 而r是使a^r同餘1(mod n)的最小整數

且a^t同餘1(mod n)  則r|t

證明: 設t=rq+s  (0<=s<r)

必有a^t同餘a^(rq+s)同餘a^(r)^q˙a^s同餘a^s同餘1(mod n)

又已知r為符合條件的最小值  故s必為0

=>t=rq  得證 r|q


證明完了  所以循環節長度r必為p-1的因數

--
※ 發信站: 批踢踢實業坊(ptt.csie.ntu.edu.tw)
◆ From: 140.112.249.46

> -------------------------------------------------------------------------- <

作者: chau (  不哭 ≠ 堅強  ) 看板: tutor
標題: Re: 請問有人知道17跟19的倍數怎麼判別嗎??
時間: Thu Jan  9 11:14:58 2003

11 是 11 的倍數 所以可以單位數減偶位數來判斷
類似的 101 可以兩位數為一單位交叉加減來判斷 EX:
abcdefg 這個7位數為101的倍數 <==> a+bc-de+fg 為 101 的倍數
這是因為 101 為 101 的倍數

1001 為 7 13 11 的倍數所以 7 11 13 這幾個數的倍數判斷方法可以是
以三位數為一單位交叉加減
10001 為 73 137 的倍數所以 73 137 這幾個數的倍數判斷方法可以是
以四位數為一單位交叉加減

一般的 如果 p 為質數且 1/p 的最小循環節位數為偶數 2n
則 p 的倍數判斷方法可以是"以 n 位數為一單位交叉加減"

這是因為 p 是 999.........9 的因數
              └ 2n 個 9 ┘

且 p 不是 999........9 的因數
          └ n 個 9 ┘

(否則 p 的最小循環節位數會是 n 而不是 2n )

因此 p 是 999.........9 / 999........9 = 1000.......001 的因數
          └ 2n 個 9 ┘   └ n 個 9 ┘   └ n-1 個 0 ┘

( p 是質數所以可以約 )

--

  循環節位數比較小的數字還有 1/37 三位 1/41 五位

--
        「miss」是想。
         也是錯失的意思
        
        「missyou」是想你。
         同時，也是錯失你。
                           

--
※ 發信站: 批踢踢實業坊(ptt.csie.ntu.edu.tw)
◆ From: 61.217.55.123
→ TwoOneboy:高手～
→ TwoOneboy:不過 p 是...的倍數要改成 p 是...的因數
→ chau: 對 謝你提醒 我改好了
> -------------------------------------------------------------------------- <

作者: chau (  不哭 ≠ 堅強  ) 看板: tutor
標題: Re: 請問有人知道17跟19的倍數怎麼判別嗎??
時間: Thu Jan  9 17:26:13 2003

還有一個不算慢的方法：

利用" 10a+b 是 19 的倍數 <==> a+2b 是 19 的倍數 "
EX：欲判斷 50008 是不是 19 的倍數
50008 是 19 的倍數
<==> 5000+16 = 5016 是 19 的倍數
<==> 501+12 = 513 是 19 的倍數
<==> 51+6 = 57 是 19 的倍數
<==> 5+14 = 19 是 19 的倍數
所以 50008 是 19 的倍數

利用" 10a+b 是 17 的倍數 <==> a+12b 是 17 的倍數 "
( 這比較麻煩因為要成以 12 )
EX：欲判斷 50008 是不是 17 的倍數
50008 是 17 的倍數
<==> 500096 = 5096 是 17 的倍數
<==> 501+72 = 573 是 17 的倍數
<==> 51+36 = 87 是 17 的倍數
<==> 8+84 = 92 是 17 的倍數
<==> 9+24 = 33 是 17 的倍數
<==> 3+3*12 = (3*13) 是 17 的倍數
所以 50008 不是 17 的倍數 (對數字熟的人最後幾步可以免了)

知道原理的可以自己推廣成自己覺得方便的形式

--

  其實 對數字熟的人.....

   每一步都可以免了 XD

--
        「miss」是想。
         也是錯失的意思
        
        「missyou」是想你。
         同時，也是錯失你。
                           

--
※ 發信站: 批踢踢實業坊(ptt.csie.ntu.edu.tw)
◆ From: 61.217.52.138

> -------------------------------------------------------------------------- <

作者: doa2 (惱人的投資學報告) 看板: tutor
標題: Re: 請問有人知道17跟19的倍數怎麼判別嗎??
時間: Thu Jan  9 18:52:06 2003

※ 引述《chau (  不哭 ≠ 堅強  )》之銘言：
: 還有一個不算慢的方法：
: 利用" 10a+b 是 19 的倍數 <==> a+2b 是 19 的倍數 "
: EX：欲判斷 50008 是不是 19 的倍數
: 50008 是 19 的倍數
: <==> 5000+16 = 5016 是 19 的倍數
: <==> 501+12 = 513 是 19 的倍數
: <==> 51+6 = 57 是 19 的倍數
: <==> 5+14 = 19 是 19 的倍數
: 所以 50008 是 19 的倍數
: 利用" 10a+b 是 17 的倍數 <==> a+12b 是 17 的倍數 "
: ( 這比較麻煩因為要成以 12 )
: EX：欲判斷 50008 是不是 17 的倍數
: 50008 是 17 的倍數
: <==> 500096 = 5096 是 17 的倍數
: <==> 501+72 = 573 是 17 的倍數
: <==> 51+36 = 87 是 17 的倍數
: <==> 8+84 = 92 是 17 的倍數
: <==> 9+24 = 33 是 17 的倍數
: <==> 3+3*12 = (3*13) 是 17 的倍數
: 所以 50008 不是 17 的倍數 (對數字熟的人最後幾步可以免了)
: 知道原理的可以自己推廣成自己覺得方便的形式
這個步驟消到百位以下就會開始繞圈圈

因為乘以十二太大

所以其實百位以下直接除了反而比較快

太拘泥於這方法也不好
--
原理

10a+b同餘20a+2b同餘a+2b(mod 19)

10a+b同餘120a+12b同餘a+12b(mod 17)

--
※ 發信站: 批踢踢實業坊(ptt.csie.ntu.edu.tw)
◆ From: 140.112.249.46

> -------------------------------------------------------------------------- <

作者: TwoOneboy (去他的死感冒) 看板: tutor
標題: Re: 請問有人知道17跟19的倍數怎麼判別嗎??
時間: Thu Jan  9 20:22:37 2003

剛剛想了想
即使我知道了一堆判別法，我可能還是會直接除而不會用判別法來判定吧
因為有些判別法也常常需要好幾個步驟
而如果一次只能消一位的話，和直接除所費的功夫是一樣的
不見得就會比直接除還快多少，而且寫起來有可能還會比較費事
再另外知道那麼多種判別法的類型其實實用性也不高

結論：暴力法硬除才是王道呀！
（如果有台計算機那更是王道中的王道呀！）

--
※ 發信站: 批踢踢實業坊(ptt.csie.ntu.edu.tw)
◆ From: 140.112.212.119
→ chau:推!!!這真是看破紅塵的見解啊.....
→ TwoOneboy:如果真的出17、19判別，只能說老師很無聊
→ chau:我還看過判斷一個八位數是否質數的題目咧
→ TwoOneboy:是那種特別形式的，還是亂出的呀？
→ TwoOneboy:我想太多了.那個數應該有3或7或11的因數吧
> -------------------------------------------------------------------------- <

作者: chau (  不哭 ≠ 堅強  ) 看板: tutor
標題: Re: 請問有人知道17跟19的倍數怎麼判別嗎??
時間: Thu Jan  9 20:39:35 2003

說起來我曾經有那麼一陣子 計算都用比較迂迴的方法呢.....
比如說 乘以九就用乘以十再減去原來的數字
乘以十則加上原來的數字
除以五我會寫成除以十再乘以二
除以二則寫成除以十再乘以五
兩個整數相成 會先分解 重新排列乘成自己熟悉的數字再乘
(比如說 二和五會先乘 二十五和四會先乘)
這樣的壞習慣可能是源自哪天用了這樣的方法佔到便宜了吧.....

用了幾個月之後發現這樣甚至比直接乘除還慢
有時候把要乘的數分解之後並不能找到自己熟悉的數 反而花更多的時間
最後就反璞歸真囉.......

不光是計算方面 有時候 那些被成為"高手"的人們
會把問題想得很難很複雜 要用XXX定理好呢 還是用XXX公式??
結果連最基本的題目都被唬住(因為用太高深的方法解不出來)
還是反璞歸真吧....
數學 是美的 是簡單的

--
        「miss」是想。
         也是錯失的意思
        
        「missyou」是想你。
         同時，也是錯失你。
                           

--
※ 發信站: 批踢踢實業坊(ptt.csie.ntu.edu.tw)
◆ From: 61.217.52.138

> -------------------------------------------------------------------------- <

作者: TwoOneboy (去他的死感冒) 看板: tutor
標題: Re: 請問有人知道17跟19的倍數怎麼判別嗎??
時間: Thu Jan  9 20:59:47 2003

: when p為質數  n^p同餘n (mod p)
: 此為Fermat定理
說到費馬小定理，我突然想到高中算mod時無意發現的一個咚咚

如果(a,b)互質，而b的質因數共有a1、a2、....an共n個
設m = b*(1-1/a1)(1-1/a2)....(1-1/an)
則a^m同餘1         (mod b)

費馬小定理是其中的一個特例
因為質數p質因數只有p
p*(1-1/p)=p-1

例如要算29^300除以100的餘數
因為100=2^2 * 5^2
100*(1-1/2)*(1-1/5) = 40
我就先假定29^40同餘1  (mod 100)
接著就算算看29^8和29^10是不是也同餘1
這樣有個目標就好算多了
這題的話29^10同餘1  (mod 100)
當然原假定29^40同餘1也是對的

我高中算題目都用這方法偷吃步
還沒碰過例外的情形
不過很可能是我題目算太少了，用程式稍微跑一跑就會有很多例外了吧

--
※ 發信站: 批踢踢實業坊(ptt.csie.ntu.edu.tw)
◆ From: 140.112.212.119
→ chau:此乃歐拉定理 m被定義成b的歐拉函數φ(b)
→ chau:φ(b) 是不大於b且與b互質的正整數個數
→ TwoOneboy:強者！  果然是我見聞淺薄呀
→ chau:沒有啦哈哈 說實在你獨立發現這個才厲害咧
→ doa2:雅賊..我們高中有算過這種題目嗎?
→ TwoOneboy:類似的有啦，而且你高一上又沒跟我同班
> -------------------------------------------------------------------------- <

作者: beckeylee (繼續掛佔五千年) 看板: tutor
標題: Re: 請問有人知道17跟19的倍數怎麼判別嗎??
時間: Fri Jan 10 18:37:19 2003

 對呀
 直接除比較快了
 如果遇到這種機車題目
 譬如問的是17的倍數的話
 題目給的數又很大
 因為已經很熟悉17的幾倍數
 17 34 51 68 85
 所以我會用題目給的數先減掉
 17000...00 或34000...00最接近的把最高位減掉
 等於反覆做兩位減法 直到剩下的數只剩五位四位
 再除一下就出來了
 如果熟的話應該會比直接除快一些些
 如果家教學生簡單心算不好計算能力不強
 那還是教他直接慢慢除

--
※ 發信站: 批踢踢實業坊(ptt.csie.ntu.edu.tw)
◆ From: 140.112.220.3

> -------------------------------------------------------------------------- <

作者: TwoOneboy (感冒好了考試爆了) 看板: tutor
標題: Re: 請問有人知道17跟19的倍數怎麼判別嗎??
時間: Sat Jan 11 13:36:40 2003

哈，我也曾經想過這些方法到底有沒有辦法簡化計算
看起來是會比較快，但實際上減去這些17的10^n倍數也就等於是做直式除法的第一步而已
所不同的是可以用心算而不需要用筆寫出來，會快一點
而且待會除的時候數字會較精簡，所以實際上是會比較快囉
但是所做的計算過程則是完全一樣的

兩位數的乘法我以前也喜歡把它拆開來算
如26*57=1000+140+300+42=1482
自以為比較快，結果後來才發現跟直式乘法完全是一模一樣的東西....-.-"

再說些無關的，我覺得算題目的速度很大一部份取決於你能一次在腦中處理多少運算過程
我常常移項、分類、去分母、約分、取log等一起來
一次跳好幾個步驟（指的是高中時的我，現在可能不行了......）
如果熟練的話，我覺得這樣子能大幅加快計算速度，也大幅減少出錯的機會
再另外的話，我高中數學老師叫我們改掉"驗算"這個"壞毛病"
要有把握一次就算對，而這樣也才能更進一步加快算題目的速度
（平常考試訓練自己就好，大考試不要，像聯考我還是給它驗算了n遍....）

這些技巧都是我高中數學老師教我的（我們都叫他賴爺爺）
非常感謝他，也非常佩服他（賴爺爺平常也對我們很好，是個好老師）
印象中他給我們考試幾乎都不帶答案的
考卷發下來他也跟著我們一起做，大約20分鐘後就看到他在看報紙了
下課後就直接以他算的答案當標準答案，三年來也幾乎沒看他計算錯誤過
印象最深的是有一次他算了30分鐘，算完後跟我們講說：
「這次考試延長20分鐘吧，因為我算了30分鐘，我想你們應該算不完」
我聽了快吐血，因為我自認算的也很快了，但是也只有算到一半而已
而那次考試延長20分鐘後還是很多人沒寫完，所以好像又有再延長
而我也是那之後才開始有在注意老師到底是啥時候算完題目的

我們高中時因為進度太快了（一星期多就可以教完一學期內容，剩下時間都在考試....）
同學們曾經想借狂問老師問題來拖慢教學進度
但後來紛紛放棄了，因為不管再龜毛的題目
老師通常也都能在一兩分鐘內算出答案
而老師寫完後，有時候我這位在班上數學還算不錯的同學連看都還沒看完.....

高中時上過不少數學老師的課，但是我覺得唯一能稱得上怪物的，只有賴爺爺了

--
※ 發信站: 批踢踢實業坊(ptt.csie.ntu.edu.tw)
◆ From: 140.112.212.119
→ doa2:推推推  賴爺爺好棒~
→ lynna:推「賴爺爺」..可是雅澤學長姓蕭？
→ lynna:對不起我錯了 (鞠躬) 我漏過一行 (哭)
→ doa2:學妹來亂的齁..
→ lynna:學妹狠認真在看文章狠感動也狠羨幕啦 >"<
→ TwoOneboy:妳實際上過賴爺爺的課再來羨慕不遲
→ TwoOneboy:兩星期上完排列組合，這沒啥好羨慕的吧...
→ TwoOneboy:而且這兩星期也不是都在上課呀.....
→ TwoOneboy:好懷念賴爺爺，他的解題法總是最漂亮的
→ doa2:就是因為不是都在上課才神奇..
→ Cid:賴....敦生?
→ TwoOneboy:不是哩，台中一中似乎沒賴敦生老師哩
→ TwoOneboy:對了，賴爺爺雖然上的很快，但卻非常詳細
→ TwoOneboy:觀念也講得非常好，真的很佩服他