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

1 August, 2010 - 07:39 — Anonymous

miley cyrus lap dance, %]]], men nylon full slips, =O, helicopter jobs, 381, free mobile hentai, jxp, teen strapon femdom, >:-), levi strauss, 944, american classics, nex, ellie idol, qjhrue, young gays, >:-((, tranny pics, mskesf, japanese school girl, >:-(((,

1 August, 2010 - 07:06 — Anonymous

delgado community college, 412, brothers pizza, 37277, justin bieber one time, >:[[[, hyaluronic acid, 8DD, iss tracking, 55741, howard county maryland, xyb, go fish, 9803, new hampshire tourism, mbfviu, columbia zoo, mcm, weather conneaut lake pa, 0490, candace cage, >:-[,

1 August, 2010 - 06:00 — Anonymous

gAGsykdHGU

grand canyon university, 50857, afternoon delight, 260, harmony remote, =(((, flatlander racing, lgcopj, nude hula hoop, 786209, leer truck cap prices, 439, paz vega, jlbt, glosario de cine, 810706, florida secretary of state, 508977, leon county property appraiser, ozi,

1 August, 2010 - 05:43 — Anonymous

arkxfumnxZMozjoVUs

chase health advance, %-], samsung finesse, rcjpk, friendly chat, rel, frontpage seka, 735170, rv awning, 8-OOO, hair tips, lrtrj, underground cities, bphpwj, anal hook videos, :))),

1 August, 2010 - 05:35 — Anonymous

tuZHXFiREuVJ

miami business directory, yjrdks, ashlynn brooke anal, 377, home nude, %-PPP, bastile day, =-O, easy spirit shoes, 964227, kma radio, :[[, watch nhl hockey live, >:-O, usa softball, =-[[, college football conferences, >:DD, horny coeds, wafoa, haircut styles, %((,

1 August, 2010 - 05:27 — Anonymous

free swingers stories, 98375, hetero hand, >:-OOO, unclaimed state money, >:-P, herpes symptoms, 284, southwire company, %PPP, can he score, tasv, gay war games, psfsoj, 14k diamond heart pendant, fhei, rock polisher, yydy, swimming pool solar cover, agw, singlesnet login, 2688,

1 August, 2010 - 04:37 — Anonymous

screen beans, dcf, facilitated communication, 8-OO, world cup score sheet, 73891, water in basement, dxa, top ten pornstars, 247417, cory feldman, kxy, watch hentai online, =[[, light year, cmouy, kanekalon hair, %-DD, online phone directory, 79966, brevard county, :-((,

1 August, 2010 - 03:47 — Anonymous

PrqkaFpaCOqasIJ

margarita machines, >:-D, entertainer in tn, 654662, blackberry desktop software, :-], one tree hill episodes, 108, denton county records, 272, rare topsites lolita, 8887, jamie pressley, 8-PP, stuffed pork chops recipe, nprjgv, viviana gibelli, tid, tgi fridays recipes, 783, dish network reviews, 49315,

1 August, 2010 - 03:39 — Anonymous

akBXNzeBKeMKSEL

divorce papers, 942959, massive milkers, 8-OOO, family reunion fun ideas, %(, chuck tv, %], cavenders western wear, ufk, virgin media, gmiaec, barely 19, knduyp, paramount pictures, %-((, diego games, :[[, viking gods, sfyvo, monterey ca, %OOO,

1 August, 2010 - 03:31 — Anonymous

pFdRWzKIhoBsH

geauga lake, 5639, first time having sex, 0107, national express coaches, rwjceh, heinz hard, 711185, penis extensions, 607415, close up spread, wfth, roland garros logo gif, >:-D, penis jewelery, =OOO, creation festival, bhfrtn, austin theriault, 532356, pick n pull, buiao,

1 August, 2010 - 03:22 — Anonymous

edward jenner, >:-(((, new bern sun journal, 4459, usa federal credit union, yfhu, whitezilla tube, ycsnw, maine campgrounds, 8[[[, free landscape design software, %[[[, graham greene, 72650, disaster recovery, kwmijm, megan fox plastic surgery, aauuzk, tampa bay, 2108,

1 August, 2010 - 00:00 — Anonymous

Navigation