Home › Blogs › pasin30055's blog

ทฤษฎีจำนวนเบื้องต้น(Number Theory) 1

30 June, 2009 - 12:04 — pasin30055

ไม่ต้องเสียเวลาแนะนำตัวผู้เขียนกันเลยล่ะกันครับ มาทำความรู้จัก”ทฤษฎีจำนวนกัน”เลยดีกว่า

ทฤษฎีจำนวน คืออะไร

ทฤษฎีจำนวน เป็นสาขาหนึ่งของคณิตศาสตร์บริสุทธิ์ ซึ่งศึกษาเกี่ยวกับคุณสมบัติของจำนวนเต็ม
ส่วนทฤษฎีจำนวนเบื้องต้นที่ผู้เขียนจะเขียนในบล็อกนี้นั้น จะเป็นความรู้พื้นฐานของทฤษฎีจำนวน ซึ่งมีเนื้อหาหลัก ๆ เช่น การหารลงตัว, ตัวหารร่วม, ตัวหารร่วมมาก, Euclidean Algorithm และอื่น ๆ ซึ่งจะเขียนครั้งเดียวก็คงจะไม่จบ ผู้เขียนจะขอค่อย ๆ แยกเขียนต่อไปเรื่อย ๆ

การหารลงตัว(Divisibility)

นิยามของการหารลงตัว : เราจะกล่าวว่าจำนวนเต็ม $ a $ หาร $ b $ ลงตัว ( $ a\mid b $ ) ถ้าเราสามารถหา $ c\in \mathbb{Z} $ ที่ทำให้ $ b=ac $
(เช่น $ 3\mid 6 $ เพราะ $ 6=3*2 $)
Note: $ \mathbb{Z} $ คือเซตของจำนวนเต็ม ,ถ้า $ a $ หาร $ b $ ไม่ลงตัวใช้สัญลักษณ์ $ a\nmid b $

สมบัติเบื้องต้น

$ 1. $ ถ้า $ a\mid b $ และ $ b\mid c $ แล้ว $ a\mid c $
$ 2. $ ถ้า $ a\mid b $ แล้ว $ a\mid bc $
$ 3. $ ถ้า $ a\mid b $ และ $ a\mid c $ แล้ว $ a\mid b+c $

Division Algorithm

ให้ $ a,b $ เป็นจำนวนเต็ม เราจะสามารถหาจำนวนเต็ม $ q $ และ $ r $ ที่ทำให้ $ b=aq+r $ และ $ 0\leqslant $ $ r < $ $ \mid a\mid $ ได้เพียงคู่เดียวเท่านั้น
(เช่น $ 7=3*2+1 $)

ข้อควรระวังในการใช้ฟังก์ชันหารเหลือเศษ(%)ในภาษาC/C++

เนื่องจากในภาษา C/C++ $ (-11) $%$ 3=-2 $ ซึ่งไม่ใช่เศษจากการหารที่แท้จริง เพราะเศษที่เราต้องการควรจะเป็น $ 1 $
เวลาเขียนโปรแกรมในการหาเศษจากการหารจึงควรเขียนเป็น

int mod(int x,int y)
{
    return (x%y+y)%y;
}
//ใช้ได้เฉพาะเมื่อ y>0 เท่านั้น

แต่ไม่ควรเขียนโค้ดเป็น
#define MOD(x,y) (x%y+y)%y

เพราะอาจทำให้เกิดปัญหาได้ เช่นถ้าเรียก
MOD(x,rand())
จะได้ค่าเป็น (x%rand()+rand())%rand()

แต่ rand() แต่ละครั้งได้ค่าไม่เท่ากัน จึงอาจเกิดปัญหาได้

ตัวหารร่วม

เรากล่าวว่า $ a $ เป็นตัวหารร่วมของ $ b $ และ $ c $ ถ้า $ a\mid b $ และ $ a\mid c $

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

นิยามของตัวหารร่วมมาก : ให้ $ a $ และ $ b $ เป็นจำนวนเต็มที่ตัวใดตัวหนึ่งไม่เป็น $ 0 $ เรากล่าวว่า $ d $ เป็นตัวหารร่วมมากของ $ a $ และ $ b $ ถ้า $ d>0 , d\mid a, d\mid b,d $ มีค่ามากที่สุดเท่าที่จะเป็นไปได้ เราใช้สัญลักษณ์ $ gcd(a,b) $ หรือ $ (a,b) $ แทนตัวหารร่วมมากของ $ a, b $
(เช่น $ 3 $ เป็นตัวหารร่วมมากของ $ 6 $ และ $ 9 $)

Euclidean Algorithm

Euclidean Algorithm เป็นขั้นตอนวิธีหาตัวหารร่วมมาก
ตัวหารร่วมมากนั้นมีสมบัติที่สำคัญที่ทำให้เกิด Euclidean Algorithm คือ
1.$ gcd(a,b)=gcd(b,a) $
2.$ gcd(a,b)=gcd(b,a $%$ b) $
เราจึงสามารถเขียนโค้ดของ Euclidean Algorithm ได้เป็น

int Euclid(int a,int b)
{
    if(b==0)
        return a;
    else
        return Euclid(b,mod(a,b));
}

ผู้เขียนก็จะขอจบการเขียน blog แรกแต่เพียงเท่านี้ แล้วต่อไปจะมาเขียนเนื้อหาในเรื่องนี้เพิ่มเติมต่อ ๆ ไป
ขอบคุณผู้อ่านทุกคนที่อุตสาห์อ่านมาจนจบ 5555