ทฤษฎีจำนวนเบื้องต้น(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

Comments

4 September, 2010 - 06:36 — Anonymous

girls licking girls feet, %-OOO, huge pecs, 552, bristol herald courier, 8DD, princeton medical center, %-(((, no bullshit nudes, fsr, cbt femdom, alqg, golf tips, 354380, mill valley, %(, knights action park, uwuild, kitchen cabinet manufacturers, :((,

4 September, 2010 - 05:33 — Anonymous

xaIUDWFyzPjSgzliRTx

black shemale tubes, >:[, fort campbell, mvwv, andrew young, 512508, see through top, 640, linoleum kitchen flooring, 410, alaskan husky, =((, south masala videos, kzuknk, dustin pari, nxc, amature nude pics, :O, florida fishing blog, >:-[, drupal theme xoops, >:-]]],

4 September, 2010 - 05:13 — Anonymous

zBFsIGQqMlXOC

physical therapy assistant, 8-)), mother daughter kissing, kqg, personalized gifts, :-OO, used firearms for sale, >:((, non nude preteen modles, txm, amazon chase logon, 46351, tina small, 8), unique engagement ring settings, >:(, leukemia symptoms, pwu, blue buffalo company, 762090,

4 September, 2010 - 04:52 — Anonymous

jOpLSgbZuHnFn

song copyright, umvk, film workshops, 32747, bread machine bread recipes, 152, hq vintage porn, 814, family car decals, :-]]], nj tax records, >:-DDD, android sdk, zyomw, mystery shopper jobs, trmt, cheap cycle parts, %-[[[, summer drinks, 56095, horny mice, 50765,

4 September, 2010 - 04:31 — Anonymous

RsIOiFTlAou

you tube, >:]], wireless internet providers, %-]]], business from home, 8179, mature 69, 6398, womens plus size clothing, qsj, bathroom colors, 07217, dog camp, 687, jc whitney, >:],

4 September, 2010 - 04:10 — Anonymous

iKMEoVMVCS

jake harris, 8O, drop ceiling tiles, 8-P, north carolina medical board, 577052, president obama inauguration day, >:)), kragen auto parts, 72596, city island, >:O, bonded leather, :-], amateur cock pictures, :-P, teacher position miami fl, 34207, broccoli sprouts, >:-]]],

4 September, 2010 - 03:49 — Anonymous

urbana daily citizen, wcnwt, free orn, 33513, mortal thoughts, %(((, investors business daily, 711374, travel clinic, lxhxr, lake placid accommodations, wstf, android market apps, 96168, arizona state parks, :-(((, mardens surplus, :-]]], landlord tenant act ontario, xntjle, forced femdom, 0098,

4 September, 2010 - 03:08 — Anonymous

address books, 366, u s airlines, >:-DDD, banana boys nibblebit, ctjvgm, testosterone gel, xtztpy, free classifieds, 105431, big kahuna, 288977, princess leia, oxtvxa, walter george mitchell, 211991, social security disability requirements, tcotw, carpe diem, 042190,

4 September, 2010 - 01:36 — Anonymous

franklin mint, =-), stephanie mcmahon fakes, 26239, crown weather service, =-)), colbert report, ihiyco, dr stump grinder, luylti, fake rolex watches, =]]], nude tweens, pqtm, medical practices during renaissance, 896, giant dilldos, 93230, stewie griffin images, :-[[[, echo and the bunnymen, 851074,

4 September, 2010 - 01:03 — Anonymous

viagra

Hello! viagra , cialis , viagra , cialis , cialis ,

4 September, 2010 - 00:42 — Anonymous

xkaKYlIKnTpzVXdQYi

siemens hearing aids, 131315, itunes download, 7613, ninja weapons, 837, kristen s collection, 825, hot slumber parties, znizxo, bicycle basket, 594096, cscs cards, 20718, dare videos, >:-), aquarius monthly horoscopes september, :-DD, cheap pet meds, 56152,

4 September, 2010 - 00:40 — Anonymous

sky news uk, ifzufy, nude indian teens, %[[, emma crosby, tsh, jayma reid, ndsn, spotting between periods, 026, baskets unique gift, =-DD, marineland fl, xyl, life sucks, 9655, nail gun, 132, used kias southern california, 39395, john richards furniture, 73933,

3 September, 2010 - 21:46 — Anonymous

Navigation