數論問題~再幫忙一下囉

[passiontcfsh 10]

1.設x，y 為正整數，x≦y，且（x，y）＝5！，【x，y】＝50！，試求這樣的數對（x，y）有多少組？

2.若自然數n使得2n＋1和3n＋1都恰好是平方數，試問5n＋3能否是一個質數？

[actino 10]

http://img696.imageshack.us/i/123jx.jpg/

答案是多少??

[core2 10]

1.設x，y 為正整數，x≦y，且（x，y）＝5！，【x，y】＝50！，試求這樣的數對（x，y）有多少組？

2.若自然數n使得2n＋1和3n＋1都恰好是平方數，試問5n＋3能否是一個質數？

以下提供個人看法供你參考。

1.設x，y 為正整數，x≦y，且（x，y）＝5！，【x，y】＝50！，試求這樣的數對（x，y）有多少組？

Sol：

依題意令x=5！h、y=5！k且（h，k）＝1，

又因為【x，y】=5！hk=50！，

所以hk=6×7×8×…×50，

我們先把大於50/2=25的質數找出，

29、31、37、41、43、47各別為一組集合共6組，

再把所有偶數(6、8、10…50)單獨成一組集合，

由於h、k互質，

故h、k其中一個數，可以視為上述的7組數字集合連乘的組合：

例如：

C(7,1)表示7組數字取1組連乘為h或k，其組合如下，

(1) h=7×9×11×…×49、k=6×8×10×…×50，

(2) h=29、k=(6×7×8×…×50)/29，

(3) h=31、k=(6×7×8×…×50)/31，

(4) h=37、k=(6×7×8×…×50)/37，

(5) h=41、k=(6×7×8×…×50)/41，

(6) h=43、k=(6×7×8×…×50)/43，

(7) h=47、k=(6×7×8×…×50)/47，

共7種不同組合。

同理可知所有組合的總合為，

C(7,1)+C(7,2)+C(7,3)+C(7,4) +C(7,5)+C(7,6)+C(7,7)

=7+21+35+35+21+7+1=127

故（x，y）共127組＃

2.若自然數n使得2n＋1和3n＋1都恰好是平方數，試問5n＋3能否是一個質數？

Sol：

設h、k屬於N，

令2n＋1=h^2…(1)，3n＋1= k^2…(2)，

又令a(3n＋1)-b( 2n＋1)= 5n＋3，

得a=-1、b=-4，

所以5n＋3=4h^2- k^2=(2h-k)(2h+k)，

因此若5n＋3為質數，

則2h-k=1，

若2h-k=1，

令h=t則k=2t-1(t屬於N)

代入(1)、(2)式得

2n+1=t^2…(3)、3n＋1=4t^2-4t+1…(4)

2(4)-3(3)消去n得5t^2-8t+3=0

因此t=3/5(不合) or 1

若t=1，

則h=1、k=1代入(1)、(2)得n=0(不合)

故知5n＋3不能是一個質數＃

此內容已被編輯, September 17, 2010 ,由 core2

[howt 10]

關於第一題，二、三樓所討論的 hk=6×7×8×…×50中共有15個質數，也就是其標準分解式由15個質數構

成，那麼(h.k)=1即是說任一質數不能同時分給h、k而已。所以等同於把15個不同質數分別放入h、k中；

又h=k顯然無解，因此h<k，換言之答案為(2^15)/2=2^14種。

[2×11×22不代表一定要分成(2×11×22，1)，也可以分成(4，121)]

第二題也感謝core大，不然我可能還在嘗試找出3x^2 - 2y^2 = 1的通解-.-..

[曾阿牛 10]

core2 大大第二題解得真是好　　讓在下受益良多

至於第一題　呃......　被 howt 大大搶先發言了　不過因為在下字都打好了　還是把在下的作法 post 出　如下

舉個簡單的例子

設 x 和 y 為正整數　且 ( x, y ) ＝ 3　且 [ x, y ] ＝ 630 ＝ 2．3^2．5．7

將 x 和 y 的寫成　

則　 可以有兩個選擇：0, 1　　 可以有兩個選擇：1, 2　

同樣的　 也都可以有兩個選擇：選最大或選最小的次數

所以　x 可以有 2^4 ＝ 16 種

如果考慮到 x ≦ y 的話　x 就有 8 ＝ 16 / 2 種 ( 直接把 16 除以 2 是因為 x 不可能等於 y

至於為什麼 x 不可能等於 y　就留給大大們自己先想想)

所以　本帖第一題這樣子的問題　跟上述的例子本質上是一樣的

我們只需知道 [ x, y ] 有幾個質因數　則答案就會是 2 的那麼多次方 再除以2

譬如上述例子 [ x, y ] 有 4 個質因數　則答案就會是 2 的那 4 次方 再除以 2 等於 8

而本帖的第二題 [ x, y ] ＝ 50! 有 15 個質因數　所以答案就是 2^14

此內容已被編輯, September 17, 2010 ,由 曾阿牛

[core2 10]

非常感謝howt大大、曾阿牛大俠，不吝指正，綜整兩位的解法，更正如下：

依題意令x=5！h、y=5！k且（h，k）＝1，

又因為【x，y】=5！hk=50！，

所以hk=6×7×8×…×50，

將hk用標準因式分解得

2^a×3^b×5^c×7^d×11^e×13^f×17^g×19^s×23^i×29^j×31^t×37^l×41^m×43^n×47^o

由於h、k互質，

所以15個質因數次方只能選擇h或k其中一個，

例如：若2^a選擇h，則k中的2質因數次方將為零(2^0=1)

以此類推，

這15個質因數次方，每一個都有兩種選擇，

所以共有2^15種選擇方式，

其中又因為x≦y故h<k，

再將h>k的組合部分去除 (正好佔一半)

故（x，y）共(2^15)/2=2^14組＃

[actino 10]

nice!!!!!!

howt大把質因數分解的概念應用到極致

解法相當乾淨