สรุปเนื้อหาเรื่อง ทฤษฎีจำนวนเบื้องต้น

การหารลงตัว

a|b หมายถึง “b หารด้วย a ลงตัว” หรือ “a หาร b ลงตัว”

b/a= c โดยที่ c เป็นจำนวนเต็ม

สมบัติ

• ถ้า a|b และ b|c แล้ว a|c
• ถ้า a และ b เป็นจำนวนเต็มบวก และ a|b แล้ว a≤b
• ถ้า a, b, c เป็นจำนวนเต็ม โดย a|b และ a|c แล้ว a|(bx+cy) เมื่อ x, y เป็นจำนวนเต็มใด ๆ

 

การหารเหลือเศษ

a/b= c เศษ d ⟶ a=b.c+d

โดยที่ a, b, c, d เป็นจำนวนเต็ม และ 0 ≤ d < |b|

คำแนะนำเพิ่มเติม :

• ถ้า a/b เหลือเศษเท่ากับ d แล้ว (m.a)/b เหลือเศษเท่ากับเศษเหลือของ (m.d)/b
• ถ้า a/b เหลือเศษเท่ากับ d แล้ว a^m/b เหลือเศษเท่ากับเศษเหลือของ d^m/b

 

จำนวนเฉพาะ

คือ จำนวนเต็มบวกที่มีแต่ 1, -1, ตัวเอง, จำนวนตรงข้ามตัวมันเอง เท่านั้นที่หารลงตัว (1 ไม่เป็นจำนวนเฉพาะ)

 

จำนวนประกอบ

คือ จำนวนเต็มบวกที่ไม่ใช่ 1 และไม่ใช่จำนวนเฉพาะ โดยสามารถเขียนจำนวนประกอบให้อยู่ในรูปจำนวนเฉพาะคูณกันได้

 

หารร่วมมาก

บทนิยาม : กำหนดให้ a,b เป็นจำนวนเต็มที่ไม่เป็นศูนย์ (อย่างน้อยที่สุดจำนวนใดจำนวนหนึ่งต้องไม่เป็นศูนย์)
แล้ว จะกล่าวว่า d ϵ I+ เป็นตัวหารร่วมมาก (Greatest Common Divisor : GCD) ของจำนวนเต็ม a,b ก็ต่อเมื่อ d เป็นจำนวนเต็มที่มากที่สุดที่ทำให้ d|a และ d|b

หมายเหตุ

• ห.ร.ม. เป็นจำนวนเต็มบวกและไม่เป็นศูนย์
• ใช้สัญลักษณ์ d = (a,b) เพื่อแสดงว่า d เป็น ห.ร.ม.ของ a และ b
• (a,b) = (-a,b) = (a,-b) = (-a.-b) นั่นคือไม่ว่าเราจะหา ห.ร.ม.ของจำนวนเต็มบวกหรือลบย่อมมีค่าเท่ากัน
• ถ้า a ไม่เป็นศูนย์แล้ว (a,0) = |a| นั่นคือ ห.ร.ม.ของจำนวนเต็มใด ๆ กับศูนย์ก็คือตัวมันเองที่เป็นบวกนั่นเอง

 

การหา ห.ร.ม. แบบยูคลิด โดยใช้ขั้นตอนวิธีการหาร

1. นำจำนวนเต็มบวกสองจำนวนที่ต้องการหา ห.ร.ม. มาคำนวณผลการและเศษเหลือจากการหาร โดยให้จำนวนมากกว่าเป็นตัวตั้งจำนวนน้อยกว่าเป็นตัวหาร ในกรณีที่จำนวนที่สนใจเป็นจำนวนเต็มลบสามารถใช้สมบัติของ ห.ร.ม. ที่กล่าวว่าห.ร.ม.ของจำนวนเต็มลบย่อมมีค่าเท่ากัน
2. นำผลจากข้อ 1. มาคำนวณอีกครั้ง โดยให้ตัวหารจากข้อ 1 เป็นตัวตั้งและเศษเหลือเป็นตัวหารคำนวณหาผลหารและเศษเหลือตัวใหม่ออกมา
3. ทำซ้ำขั้นตอนที่ 2 ไปเรื่อย ๆ จนกว่าจะหารลงตัว
4. ห.ร.ม. จะเท่ากับเศษเหลือตัวสุดท้ายที่เกิดขึ้น ซึ่งเหลืออยู่ก่อนบรรทัดสุดท้าย

 

ตัวคูณร่วมน้อย

นิยาม : ให้ a และ b เป็นจำนวนเต็ม โดยที่ a,b ไม่เป็นศูนย์พร้อมกัน จำนวนเต็มบวก c ที่น้อยที่สุดที่ทำให้ a|c และ b|c เรียกว่าเป็น ตัวคูณร่วมน้อย หรือ ค.ร.น. นั่นเอง

หมายเหตุ :

• ค.ร.น.เป็นจำนวนเต็มบวกและไม่เป็นศูนย์
• ใช้สัญลักษณ์ [a,b] =C เพื่อแสดงว่า c เป็น ค.ร.น. ของ a และ b
• [a,b] = [a,-b]= [-a,b)= [-a,-b] นั่นคือไม่ว่าเรา
• จะหา ค.ร.น.ของจำนวนเต็มบวกหรือลบย่อมมีค่าเท่ากัน
• [0,a]=0