ตัวหารร่วมมาก (ห.ร.ม.)

ตัวหารร่วมมาก

นิยาม    กำหนดให้ a, b เป็นจำนวนเต็ม , a ≠oหรือ b ≠o ,  ตัวหารร่วมมาก (ห.ร.ม., greatesr common division : gcd  )ของ a และ b  คือจำนวนเต็มบวก d จำนวนเดียวเท่านั้นที่ใหญ่ที่สุดซึ่งมีคุณสมบัติว่า d | a  และ  d | b

ต่อไปจะเขียนแทน ห.ร.ม. ของ a และ b ด้วยสัญลักษณ์ gcd (a , b)

ตัวอย่าง  จงหาห.ร.ม. ของ 24 และ 36

วิธีทำ

                ตัวหารร่วมของ 24 และ 36 คือ 1, 2, 3, 4, 6 และ 12

                ดังนั้น gcd(24, 36) = 12

ตัวอย่าง  จงหาห.ร.ม. ของ 17 และ 22

วิธีทำ

                ตัวหารร่วมของ 17 และ 22 คือ 1

                ดังนั้น gcd (17, 22) = 1

นิยาม จำนวนเต็ม a และ b จะเรียกว่า relatively prime ถ้า ห.ร.ม. ของ a และ b คือ 1

ตัวอย่าง  

เนื่องจาก  gcd(17, 22) = 1

ดังนั้น 17 และ 22 เป็น relatively prime

นิยาม จำนวนเต็ม a₁, a₂, … a_nจะเรียกว่า pairwise relatively prime ถ้า gcd(a_i , a_j) = 1

ตัวอย่าง  จงตรวจสอบว่า 10, 17, 21 เป็น pairwise relatively prime หรือไม่

เนื่องจาก  gcd(10, 17) = 1, gcd(10, 21) = 1, gcd(17, 21) = 1

ดังนั้น 10, 17 และ 21 เป็น pair wise relatively prime

การหา ห.ร.ม.

                a  =  p₁^a1 p₂ ^a2…p_n ^an     , b = p₁^b1 p₂ ^b2…p_n ^bn

ดังนั้น

                gcd(a, b) = p₁^{min(a1, b1)} p₂ ^min(a2,b2)…p_n ^{min(an, bn)}

 ตัวอย่าง จงหา หรมของ 120 และ 500

\120 = 2³.3 .5 และ 500 = 2².5³

                ดังนั้น gcd (120, 500) = 2^{min(3,  2)} 3 ^{min(1, 0)}…5 ^{min(1, 3)} = 2²3⁰5¹ = 20

นิยาม     กำหนดให้ a, b เป็นจำนวนเต็ม , a≠o หรือ b≠o ตัวคูณร่วมน้อย  (ค.ร.น. , least common multiple :  lcm ) ของ a และ b คือจำนวนเต็มบวก m ที่เล็กที่สุดจำนวนเดียวเท่านั้น ซึ่งมีคุณสมบัติว่า a | m   และ  b | m

ต่อไปจะเขียนแทน ค.ร.ม. ของ a และ b ด้วยสัญลักษณ์  lcm (a , b)

ถ้ากำหนด

a  =  p₁^a1 p₂ ^a2…p_n ^an     , b = p₁^b1 p₂ ^b2…p_n ^bn

ดังนั้น

                lcm(a, b) = p₁^{max(a1, b1)} p₂ ^{max(a2, b2)}…p_n ^{max(an, bn)}

ตัวอย่าง  จงหา ค.ร.น.ของ  2³.3⁵ .7² และ 2⁴.3³

                ดังนั้น lcm (2³.3⁵ .7² ,  2⁴.3³) = 2^{max(3,  4)} 3 ^{max(5, 3)}…7 ^{max(2, 0)} = 2⁴3⁵7²

 ขอขอบคุณ staff.buu.ac.th/~seree/310213/chap05.doc

การแยก อัลกอริทึม

Division Algorithm

ทฤษฎี (Division Algorithm) ถ้า a และ d  เป็นจำนวน ซึ่ง d  > 0 แล้ว แล้วมีจำนวนเต็ม q และ r คู่หนึ่งและคู่เดียวเท่านั้น  ซึ่งมีคุณสมบัติว่า

                                a =  dq + r       ,    0 ≤ r < d

                      (ในที่นี้การพิสูจน์จะเว้นไว้)

หมายเหตุ  จากทฤษฎี  ซึ่งได้กล่าวว่า สำหรับทุกๆ a,d € Z , d > 0 จะมี q,r € Z  ซึ่งมีคุณสมบัติว่า 

 a = dq + r   , 0≤ r < d

                เราเรียก  a  ว่า ตัวตั้ง(dividend)

                เรียก  d ว่า  ตัวหาร(divisor) ในการหาร a ด้วย d

                เรียก  q ว่า  ผลตัวหาร(quotient) ในการหาร a ด้วย d

                และเรียก r  ว่า เศษ (remainder)    ในการหาร a ด้วย d

         เราจะเห็นได้ชัดว่า  d เป็นตัวหารที่ลงตัว  ของ a  ก็ต่อเมื่อเศษในการหาร  a  ด้วย  d เท่ากับ 0

                ถ้าทั้ง a และ d เป็นจำนวนเต็มบวกทั้งคู่  แล้วผลหาร และเศษในการหาร a ด้วย  d  อาจจะหาได้โดยวิธีการหารยาวในทางเลขคณิต

ตัวอย่าง  จงหาผลหารและเศษจาการหาร 101 ด้วย 11

วิธีทำ

                101= 11. 9  + 2

                ดังนั้นเศษคือ 2 และผลหารคือ 9

ตัวอย่าง  จงหาผลหารและเศษจาการหาร -11 ด้วย 3

วิธีทำ

                -11= 3(-4)  + 1

                ดังนั้นเศษคือ 1 และผลหารคือ -4

 ข้อสังเกตุ เศษที่เหลือจากการหารจะไม่เป็นจำนนวนลบ จากตัวอย่างข้างต้น เศษที่เเหลือจากการหารจะไม่เป็น -2 ถึงแม้ว่า -11 = 3(-3) - 2 เนื่องจาก r = -2 จะไม่สอดคล้องกับเงื่อนไขที่กล่าวว่า

 0≤ r < 3

ขอขอบคุณ staff.buu.ac.th/~seree/310213/chap05.doc

การหารที่ลงตัว และ Division Algorithm

นิยาม  สำหรับทุกๆ a , bเป็นจำนวนเต็ม  ซึ่ง a ≠ 0ในกรณีที่ a เป็นตัวหารที่ลงตัวหรือ แฟกเตอร์ ของ b  เราอาจกล่าวได้อีกอย่างหนึ่งว่า

                                a หาร b ได้ลงตัว                                

                                b หารด้วย a  ได้ลงตัว

                                b เป็น multiple ของ a

                สัญลักษณ์ที่ใช้เขียนแทน ” a เป็นตัวหารที่ลงตัวของb “ เรานิยมเขียนแทนด้วย a | b และในกรณีที่ a ไม่เป็นตัวหารที่ลงตัวของ b  เราเขียนแทนด้วยสัญลักษณ์ a \/ b

                จะสังเกตว่าจากนิยาม ตัวหารที่ลงตัวจะต้องไม่เท่ากับ 0 เสมอ ดังตัวอย่าง ถ้าเราเขียนว่า

x | y    เป็นที่เข้าใจกันว่า x ≠ 0 

ทฤษฎี  ให้ a , c และ b เป็นจำนวนเต็มใด ๆ จะได้

1.        ถ้า a | b และ a | c แล้ว a | (b + c)

2.        ถ้า a | b แล้ว a | bc สำหรับจำนวนเต็มใด ๆ

3.        ถ้า a | b และ b | c แล้ว a | c

พิสูจน์    1.

                สมมุติให้  a | b และ a | c

                ดังนั้นจากนิยามของการหารลงตัวจะได้ว่ามีจำนวน s และ t ซึ่งทำให้  b= as และ c = at

                  b + c = as + at = a (s + t)

                นั่นคือ  a | (b + c)

ข้อ 2 และ 3 ให้เป็นแบบฝึกหัด

นิยาม     ให้ p เป็นจำนวนเต็มบวกใด ๆ ซึ่ง p > 1 จะเรียกว่าจำนวนเฉพาะ(prime)ก็ต่อเมื่อแฟกเตอร์ของ p คือ  1 และ p เท่านั้น และจะเรียกจำนวนเต็มบวกที่มากกว่า 1 และไม่เป็นจำนวนเฉพาะว่า composite

ตัวอย่าง  7 เป็นจำนวนเฉพาะ

                9 เป็น composite เนื่องจากหารด้วย 3 ลงตัว

ขอขอบคุณ staff.buu.ac.th/~seree/310213/chap05.doc