[問題][數學]最大質因數

[問題][數學]最大質因數

黃阿揚 於 星期日 九月 04, 2005 2:15 pm


求9^6-7^5的最大質因數


今年剛剛高一
不知道用什麼方法比較好
請各位教教我好嗎
有重複貼的話先說抱歉一下

黃阿揚
實習生
實習生
 
文章: 50
註冊時間: 2004-09-24

chanjunhong 於 星期二 九月 06, 2005 12:00 am


不好做,有點偷吃步,
另10=x

展開整理,裡面有點小技巧,例如最後常數項244=2x^2+4x+4
整理後得5x^5+x^4+4x^3+6x^2+3x+4=514634=2x257317=2X19X29X467
所以最大的是467,
還好不用檢查前面,同時你可以採用7、11、13的判別法則,都不會是因數,只檢查一下
17和23後就得到19和29兩個因數,再檢查467是不是質數就好,如果都是大整數的質數,建議你可採用密法學的檢驗方式,看過但是沒記過,
還有原本想嘗試對多項式轉換2進位後做Galois分解,但是抱歉學藝不精,忘記怎麼做
如果有人記得,可以說一下嗎?(當然不確定是否可做,真的忘了抱歉)
同時是否有更好的作法,分享一下吧!!

chanjunhong
實習生
實習生
 
文章: 93
註冊時間: 2005-07-25

galaxylee 於 星期二 九月 06, 2005 12:24 am


才高一而已,就只有乘開直接分解吧
還好質因數19及29還不會很大
最後留下467,因為√467=21.---小於29
用質數判別法,只需檢驗19即可知道467是質數

galaxylee
副教授
副教授
 
文章: 555
註冊時間: 2005-07-18

lcflcflcf 於 星期二 九月 06, 2005 12:33 am


我也才中四(香港的中四是否等於台灣的高一?)而已...
但想知除了乘開再試用質數除這方法外
還有什麼方法?

之前想過這題
但只知可以試
卻不知有否其他方法...
我還不是真的去試...用程式求...........

PS本人總覺得"試"不是個好方法...:p
我認為數學其中一個最美的就是有漂亮的解...
人人為我 我為人人
~就讓一切隨風~

lcflcflcf
教 授
教 授
 
文章: 887
註冊時間: 2004-10-30
來自: HK

chanjunhong 於 星期二 九月 06, 2005 1:01 am


galaxylee 寫到:才高一而已,就只有乘開直接分解吧
還好質因數19及29還不會很大
最後留下467,因為√467=21.---小於29
用質數判別法,只需檢驗19即可知道467是質數


我想我的作法應概和你一樣是直接做,但是在做的過程中
會遇257317是不是質數這個問題,257317要開根號值是500......
這樣大的整數,你要檢查1-500中的所有質數,當倒楣時是一件不容易的事,
我所指的是,當倒楣時怎麼辦?是否有替代的方案,
而Galois分解及密法學的檢驗方式的提出,是意味瞭解這些方法的人,
是否可以簡易的說明一下或可參考的網頁或書,是否可行?我想多瞭解一件事,並不需考量身份吧!而且質數的發展以經到判斷大整數是否是質數,大質數如何有效的去找,和判斷?同時,這一題不也是一個很好的範例說明一件事,利用開根號判斷質數的方式的方式,只比篩選法有效率,難到就再沒有比開根號判別質數更有效率的方式嗎?

以上的言論僅傳達,自己個人的理念及想法,無批判任何人的意思,
若言論有不妥的地方,請多多見諒,也請不吝惜指教,感謝各位

chanjunhong
實習生
實習生
 
文章: 93
註冊時間: 2005-07-25

J+W 於 星期二 九月 06, 2005 1:43 am


chanjunhong 寫到:
galaxylee 寫到:才高一而已,就只有乘開直接分解吧
還好質因數19及29還不會很大
最後留下467,因為√467=21.---小於29
用質數判別法,只需檢驗19即可知道467是質數


我想我的作法應概和你一樣是直接做,但是在做的過程中
會遇257317是不是質數這個問題,257317要開根號值是500......
這樣大的整數,你要檢查1-500中的所有質數,當倒楣時是一件不容易的事,
我所指的是,當倒楣時怎麼辦?是否有替代的方案,
而Galois分解及密法學的檢驗方式的提出,是意味瞭解這些方法的人,
是否可以簡易的說明一下或可參考的網頁或書,是否可行?我想多瞭解一件事,並不需考量身份吧!而且質數的發展以經到判斷大整數是否是質數,大質數如何有效的去找,和判斷?同時,這一題不也是一個很好的範例說明一件事,利用開根號判斷質數的方式的方式,只比篩選法有效率,難到就再沒有比開根號判別質數更有效率的方式嗎?

以上的言論僅傳達,自己個人的理念及想法,無批判任何人的意思,
若言論有不妥的地方,請多多見諒,也請不吝惜指教,感謝各位



1。您第一次提出的方法很不錯,能再詳細說明嗎?

2。另外關於會遇257317是不是質數這個問題

那就必須用到判定19的倍數的方法
1X2+2X5+4X7+8X3+16X1+32X7=304
304÷19=16
257317÷19=13543
19試完試試23,29。。。

http://www.mathland.idv.tw/life/19mult.htm

J+W
版 主
版 主
 
文章: 2165
註冊時間: 2003-12-30

訪客 於 星期二 九月 06, 2005 4:49 am


展開後得:













最後整理得:

訪客

 

chanjunhong 於 星期二 九月 06, 2005 5:10 am


Anonymous 寫到:展開後得:













最後整理得:


抱歉忘記登入,我之前希望這裡可以做因式分解開來,但轉換成10進位的多項式後,要求質多項式,不知道要怎麼分解,所以才想轉到Galois的方式來做,但是忘記怎做,也不知道可不可行,所以最後才還原整數,但是這樣大的整數馬上面對大整數的分解,這個技巧是密碼學入門所要先會的,,同時上次坐火車時翻了一下密碼學的介紹書,好像有一個方法不錯,所以才有這樣的建議,可是剛剛閱讀一下相關網頁,其實在人工的計算上好像都不好做,所以收回前言,有在閱讀到在分享給各位,也請各位不吝惜分享作法,感謝各位。

chanjunhong
實習生
實習生
 
文章: 93
註冊時間: 2005-07-25

黃阿揚 於 星期二 九月 06, 2005 10:18 pm


圖看不到喔
所以不知道你們說什麼
抱歉喔

黃阿揚
實習生
實習生
 
文章: 50
註冊時間: 2004-09-24

J+W 於 星期三 九月 07, 2005 12:35 am


黃阿揚 寫到:圖看不到喔
所以不知道你們說什麼
抱歉喔


那個得下載 java 的軟體 ,站內有連結,但是好像有和舊版的注音輸入法衝突
像我的就會,有時得等上好一陣子才能回復文章

目前的結論是直接展開去分解是最快的方法
 6  5
9 -7 =531441-16807=514634

2│ 514634 →容易判斷出有2的因數
 └───────
19│257317 →參考上面文章的19的倍數判斷法
  └──────
 29│13543 →參考下面的29的倍數判斷法或者直接除
   └──────
      467 →可以試驗出是質數

29的倍數判斷法:

例:13543

數的位值  1   3   5   4   3
3的次方  1   3   9  27  81
兩者相乘  1   9  45 108 243
全部總合 1+9+45+108+243=406
     406/29=14---是29的倍數

原理和19的倍數判斷法相同!請參考我之前發的文章的連結!

J+W
版 主
版 主
 
文章: 2165
註冊時間: 2003-12-30

chanjunhong 於 星期四 九月 08, 2005 7:09 am


終於找到啦,介紹一個大數分解法
費馬的大數分解法:





257317=(509-42)(509+42)=467*551



24*24-551=5*5

551=(24+5)(24-5)=29*19

大家可以去查一下,中間有些計算有少,請見諒,
我把原文的範例打在下面:
n=13837



118^(2)-13837=87 is not square
119^(2)-13837=324=18^(2)  is squre
so,  13837=(119+18)(119-18)=137*101  both numbers are prime numbers.

出處:台北師範學院學報  民83  25期  457-464
作者:張莉莉
如果還有找到不錯的方法,在分給大家吧

打完後,有點後悔,這個方法和平方數法好像沒什麼兩樣,
但是目前找的到,可用的方法,而且無保密條款、、、等相關限制的只有這一篇,
各位抱歉阿,我在努力找看看有沒有更好的方法

chanjunhong
實習生
實習生
 
文章: 93
註冊時間: 2005-07-25

J+W 於 星期四 九月 08, 2005 7:22 am


chanjunhong 寫到:終於找到啦,介紹一個大數分解法
費馬的大數分解法:





257317=(509-42)(509+42)=467*551



24*24-551=5*5

551=(24+5)(24-5)=29*19

大家可以去查一下,中間有些計算有少,請見諒,
我把原文的範例打在下面:
n=13837



118^(2)-13837=87 is not square
119^(2)-13837=324=18^(2)  is squre
so,  13837=(119+18)(119-18)=137*101  both numbers are prime numbers.

出處:台北師範學院學報  民83  25期  457-464
作者:張莉莉
如果還有找到不錯的方法,在分給大家吧


真是太感謝您分享如此美妙的算法了!
真沒想到居然是利用如此平凡的平方差公式!
還好這次的計算並不複雜,不會發生沒有位置記下來的情形!

J+W
版 主
版 主
 
文章: 2165
註冊時間: 2003-12-30

黃阿揚 於 星期六 九月 10, 2005 11:02 am


這個方法正是棒
今天又學到一招了
不過啊 好像要分解514634好像很麻煩的

黃阿揚
實習生
實習生
 
文章: 50
註冊時間: 2004-09-24






高中數學問題