ความคิดเห็นที่ 9
ตัวอย่างการหา ห.ร.ม ของ 1,160,718,174 กับ 316,258,250
1,160,718,174 = 3(316,258,250) + 211943424
316,258,250 = 1(211943424) + 104314826
211943424 = 2(104314826) + 3313772
104314826 = 31(3313772) + 1587894
3313772 = 2(1587894) + 137984
1587894 = 11(137984) + 70070
137984 = 1(70070) + 67914
70070 = 1(67914) + 2156
67914 = 31(2156) + 1078
2156 = 2(1078) + 0
ทำไปเรื่อย ๆ แบบที่ทำให้ดู บรรทัดสุดท้ายจะถึงศูนย์ในที่สุดไม่เกิน 2log2b ขั้น (เมื่อ a > b > 0) เลขตัวท้ายสุดของบรรทัดก่อนเป็นศูนย์จะเป็น ห.ร.ม.
นั่นคือในที่นี้ gcd( 1,160,718,174 , 316,258,250) = 1708
Note
1. gcd(a,b) = gcd(-a,b) = gcd(a,-b) = gcd(-a,-b)
2. gcd(a,b,c) = gcd((a,b),c) โดยทั่วไป gcd(a1, a2, ... , an) = gcd((a1, (a2, ... , an)) เมื่อ n เป็นจำนวนเต็มบวกที่มากกว่าหรือเท่ากับ 2
จากคุณ :
mrgon 
- [
3 ธ.ค. 47 00:43:36
]
|
|
|
