ทฤษฎีจำนวนเบื้องต้น

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

นิยาม : ให้ m และ n เป็นจำนวนเต็ม
โดยที่ n หาร m ลงตัว ก็ต่อเมื่อ มีจำนวน q ที่ทำให้ m = nq
เรียก n ว่าเป็น ตัวหาร ของ m และ
เรียก m ว่าเป็นพหุคูณ ของ n

จากนิยามดังกล่าว มีการใช้สัญลักษณ์ ดังนี้

n|m แทน n หาร m ลงตัว หรือ m หารด้วย n ลงตัว
n|/m แทน n หาร m ไม่ลงตัว หรือ m หารด้วย n ไม่ลงตัว

การหารลงตัว

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

สมบัติ

• [a,b,c] = [[a,b],c] = [a,[b,c]]
• ถ้า a|n และ b|n จะได้ว่า [a,b]|n

สมบัติของ ห.ร.ม. และ ค.ร.น.

ให้ a,b เป็นจำนวนเต็ม d= (a, b) , c = [a,b] จะได้ว่า dc = |ab|

จำนวนเฉพาะสัมพัทธ์

คือจำนวนเต็ม 2 จำนวน ที่มี ห.ร.ม. เท่ากับ 1 ดังนั้น จำนวนเต็มสองจำนวนนั้นจะไม่มีตัวประกอบร่วมกัน

สมการไดโอแฟนไทน์

นิยาม : สมการไดโอแฟนไทน์ (Diophantine Equation) คือ สมการที่มีตัวแปรที่เกี่ยวข้องมากกว่าหนึ่งตัว และมีผลเฉลยเป็นจํานวนเต็ม

สมการไดโอแฟนไทน์เชิงเส้น

สมการไดโอแฟนไทน์เชิงเส้น (Linear Diophantine Equation) คือสมการไดโอแฟน ไทน์ที่อยู่ในรูป a1x1+a2x2+a3x3+… +anxn =b เป็นจำนวนเต็ม และ a1, a2, a3 ,…, an, b เป็นจำนวนเต็มที่ไม่เป็นศูนย์และเป็นตัวแปรซึ่งมีผลเฉลยเป็นจํานวนเต็ม

ตัวอย่างข้อสอบ ทฤษฎีจำนวนเบื้องต้น

1. สำหรับจำนวนเต็ม a,b ใด ๆ ให้ (a,b) =ห.ร.ม. ของ a และ b
ให้ A={1,2,3…, 400}
จำนวนสมาชิกของเซต {x ϵ A|(x,40) = 5} มีค่าเท่ากับข้อใดต่อไปนี้

ก. 30
ข. 40
ค. 60
ง. 80

2. จำนวนสมาชิกในเซต {100,101,102, …., 600) ซึ่งหารด้วย 8 หรือ 12 ลงตัว เท่ากับข้อใดต่อไปนี้

ก. 84
ข. 92
ค. 100
ง. 125

3. ข้อความในข้อใดต่อไปนี้ผิด

ก. ถ้า a, b,n เป็นจำนวนเต็มบวก ซึ่ง n|a และ n|b แล้วจะได้ว่า n หาร ห.ร.ม. ของ a,b ลงตัวด้วย
ข. ถ้า a, b,n เป็นจำนวนเต็มบวก ซึ่ง a|n และ b|n แล้วจะได้ว่า ค.ร.น. ของ a,b หาร n ลงตัวด้วย
ค. ถ้า a, m,n เป็นจำนวนเต็มบวก และ a|mn แล้วจะได้ a|m หรือ a|n
ง. ถ้า d และ c เป็น ห.ร.ม. และ ค.ร.น. ของจำนวนเต็มบวก m, n แล้วจะได้ว่า dc = mn

4. n เป็น ห.ร.ม. ของ 14097 และ 14351 จำนวนในข้อใดต่อไปนี้หารด้วย n แล้วได้เศษเหลือเป็นจำนวนเฉพาะ

ก. 135
ข. 144
ค. 162
ง. 153

5.ข้อใดคือจำนวนเต็มบวกที่มีค่าน้อยที่สุดที่หารด้วย 12, 18, 20 ลงตัว

ก. 36
ข. 240
ค. 180
ง. 120