Damcaniaeth rhifau

Nodyn:Pethau Cangen o fathemateg bur yw damcaniaeth rhifau (neu theori rhif), sef yr astudiaeth o briodweddau rhifau. Cyfanrifau yw canolbwynt y maes, ond fe gyfyd problemau ehangach wrth eu hastudio, sy'n cysylltu damcaniaeth rhifau â sawl cangen arall o fathemateg. Dywedodd y mathemategydd Carl Friedrich Gauss (1777-1855), "Mathemateg yw Brenhines y gwyddorau - a theori rhif yw Brenhines mathemateg."Nodyn:Sfn Mae maes damcaniaethwyr rhif yn cynnwys rhifau cysefin, nodweddion gwrthrychau a wnaed o rifau cymarebol a chyfanrifau alegbraidd.

Ni ddylid cymysgu damcaniaeth rhifau a rhifyddeg elfennol, sef dulliau o adio, tynnu, a lluosi. Hyd at ddechrau'r 20g y term a ddefnyddiwyd am y ddamcaniaeth rhifau oedd "rhifyddeg".

Mae dosbarthiad rhifau cysefin yn bwynt astudio canolog mewn theori rhif. Mae'r tsbeiral Ulam hwn yn ei ddangos, gan awgrymu'r annibyniaeth amodol rhwng bod yn gysefin a bod yn werth o fewn rhai polynomialau cwadratig penodol.

Yr hen derm am theori rhif yw rhifyddeg. Erbyn dechrau'r 20g, roedd "theori rhif" wedi disodli'r term hwn. Defnyddir y gair "rhifyddeg" gan y cyhoedd i olygu "cyfrifiadau elfennol"; mae hefyd wedi caffael ystyron eraill mewn rhesymeg fathemategol, fel gyda rhifyddeg Peano, a gwyddoniaeth gyfrifiadurol, rhifyddeg pwynt arnofio. Adferwyd y defnydd o'r term rhifyddeg ar gyfer theori rhif am ychydig yn ail hanner yr 20g, yn rhannol oherwydd dylanwad Ffrainc.

Hanes

Gwreiddiau

Tabled Plimpton 322

Mae'r darganfyddiad hanesyddol cynharaf o natur rifyddeg yn ddarn o fwrdd: mae'r dabled clai toredig Plimpton 322 (Larsa, Mesopotamia, ca. 1800 CC) yn cynnwys rhestr o "Driawdau Pythagoraidd", hynny yw, cyfanrifau $(a,b,c)$ fel bod $a^2+b^2=c^2$. Mae'r triawdau'n ormod ac yn rhy fawr i'w cael gan rym yn unig. Mae'r pennawd dros y golofn gyntaf yn darllen: "Mae Takiltum y groeslin sydd wedi'i dynnu fel bod y lled.."

Mae cynllun y tabl yn awgrymu iddo gael ei adeiladu trwy'r hyn sy'n cyfateb, mewn iaith fodern, i'r unfathiant.

${\left(\frac{1}{2}(x-\frac{1}{x})\right)}^2+1={\left(\frac{1}{2}(x+\frac{1}{x})\right)}^2,$

sy'n digwydd yn naturiol o fewn ymarferion yr Hen Fabiloniaid.Nodyn:Sfn Pe bai rhyw ddull arall yn cael ei ddefnyddio, adeiladwyd y triawd yn gyntaf ac yna eu hail-osod gan $c/a$, yn ôl pob tebyg at ddefnydd gwirioneddol fel "tabl", er enghraifft, gyda golwg ar ei gymwyso mewn modd ymarferol.

Nid yw'n hysbys pa fath o gymwysiadau. Dim ond yn ddiweddarach y daeth seryddiaeth Babilonaidd. Awgrymwyd yn hytrach bod y tabl yn ffynhonnell o enghreifftiau rhifiadol ar gyfer problemau ysgol.Nodyn:Sfn

Er bod theori rhif Babilonaidd yn cynnwys y darn sengl trawiadol hwn, roedd algebra Babilonaidd (yn yr ystyr ysgol uwchradd o " algebra ") wedi'i ddatblygu'n eithriadol o dda.Nodyn:Sfn Nodir o fewn ffynonellau Neoplatonig hwyr bod Pythagoras wedi dysgu mathemateg gan y Babiloniaid. Mae ffynonellau llawer cynharach yn nodi bod Thales a Pythagoras wedi astudio yn yr Aifft. .

Siaradodd y traddodiad Pythagoreaidd hefyd am yr hyn a elwir yn niferoedd polygonal neu ffigurol (figurate numbers).Nodyn:Sfn Er bod rhifau sgwâr, rhifau ciwbig, ac ati, bellach yn cael eu hystyried yn fwy naturiol na rhifau trionglog, rhifau pentagonal, ac ati, byddai astudio symiau rhifau trionglog a phentagonol yn cael ei gymeradwyo yn y cyfnod modern cynnar (17g i dechrau'r 19g).

Ni wyddom am unrhyw ddeunydd rhifyddol amlwg yn ffynonellau hynafol yr Aifft neu Veda, er bod rhywfaint o algebra ym mhob un. Mae'r theorem gweddill Tsieineaidd yn ymddangos fel ymarfer yn Sunzi Suanjing (3g, 4g neu 5g).

Mae rhywfaint o gyfriniaeth rifiadol hefyd mewn mathemateg Tsieineaidd, ond, yn wahanol i rai'r Pythagoreaid, ymddengys nad yw wedi arwain i unman. Fel rhifau perffaith y Pythagoriaid, mae sgwariau hud wedi pasio o ofergoeliaeth i hwyl a hamdden.

Gwlad Groeg Clasurol a'r cyfnod Hellenistig cynnar

Ar wahân i ychydig o ddarnau, mae mathemateg Gwlad Groeg Clasurol yn hysbys i ni naill ai trwy adroddiadau pobl nad ydynt yn fathemategwyr cyfoes neu trwy weithiau mathemategol o'r cyfnod Helenistaidd cynnar.Nodyn:Sfn Yn achos theori rhif, mae hyn yn golygu, ar y cyfan, Plato ac Euclid.

Tra bod mathemateg Asiaidd wedi dylanwadu ar ddysgu Groeg a Helenistaidd, mae'n ymddangos bod mathemateg Gwlad Groeg hefyd yn draddodiad brodorol.

Mae Eusebius, PE X, pennod 4 yn sôn am Pythagoras :

"Mewn gwirionedd ymwelodd y Pythagoras dywededig, wrth astudio doethineb pob cenedl yn brysur, â Babilon, a'r Aifft, a Phersia cyfan, gan gael ei gyfarwyddo gan y Magi a'r offeiriaid: ac yn ychwanegol at y rhain dywedir iddo astudio o dan y Brahmans (athronwyr Indiaidd yw'r rhain); a chasglodd sêr-ddewiniaeth gan rai, oddi wrth eraill geometreg, a rhifyddeg a cherddoriaeth gan eraill, a gwahanol bethau o wahanol genhedloedd, a dim ond gan ddynion doeth Gwlad Groeg na chafodd ddim, gan iddynt briodi tlodi a phrinder doethineb: felly i'r gwrthwyneb daeth ef ei hun yn awdur cyfarwyddyd i'r Groegiaid yn y ddysg yr oedd wedi'i gaffael o dramor."

Honnodd Aristotle fod athroniaeth Plato yn dilyn dysgeidiaeth y Pythagoriaid yn agos, ac mae Cicero'n ailadrodd yr honiad hwn: Platonem ferunt didicisse Pythagorea omnia ("Maen nhw'n dweud bod Plato wedi dysgu popeth Pythagoraidd").

Roedd gan Plato ddiddordeb mawr mewn mathemateg, ac roedd yn gwahaniaethu'n glir rhwng rhifyddeg a chyfrifo. Trwy un o ddeialogau Plato - sef Theaetetus - y gwyddom fod Theodorus wedi profi fod $\sqrt{3},\sqrt{5},\dots ,\sqrt{17}$ yn afresymol. Roedd Theaetetus, fel Plato, yn ddisgybl i Theodorus; gweithiodd ar wahaniaethu gwahanol fathau o "incommensurables", ac felly gellir dadlau ei fod yn arloeswr wrth astudio systemau rhif. Mae Llyfr X o Elfennau Euclid yn cael ei ddisgrifio gan Pappus fel un sy'n seiliedig i raddau helaeth ar waith Theaetetus.

Neilltuodd Euclid ran o'i Elfennau i rifau cysefin a rhannu, pynciau sy'n perthyn yn ddiamwys i theori rhif ac sy'n sylfaenol iddi (Llyfrau VII i IX o Elfennau Euclid). Yn benodol, rhoddodd algorithm ar gyfer cyfrifiadura'r rhannwr cyffredin mwyaf o ddau rif (yr algorithm Ewclidaidd; Elements, Prop. VII.2) a'r prawf hysbys cyntaf o anfeidredd rhifau cysefin (Elfennau, Prop. IX.20).

Yn 1773, cyhoeddodd Lessing epigram yr oedd wedi dod o hyd iddo mewn llawysgrif yn ystod ei waith fel llyfrgellydd; honnodd ei fod yn llythyr a anfonwyd gan Archimedes at Eratosthenes.Nodyn:SfnNodyn:Sfn Cynigiodd yr epigram yr hyn a elwir bellach yn "broblem gwartheg Archimedes"; mae ei ddatrysiad (yn absennol o'r llawysgrif) yn gofyn am ddatrys hafaliad cwadratig amhenodol (sy'n lleihau i'r hyn a fyddai wedyn yn cael ei gam- enwi'n 'hafaliad Pell'). Hyd y gwyddom, cafodd hafaliadau o'r fath eu trin yn llwyddiannus yn gyntaf gan yr ysgol Indiaidd. Nid yw'n hysbys a oedd gan Archimedes ei hun ddatrysiad i'r broblem.

Diophantus

Clawr rhifyn 1621 o Arithmetica gan Diophantus, wedi'i gyfieithu i'r Lladin gan Claude Gaspard Bachet de Méziriac .

Ychydig iawn sy'n hysbys am Diophantus o Alexandria; mae'n debyg ei fod yn byw yn y 3g OC, hynny yw, tua phum can mlynedd ar ôl Euclid. Mae chwech allan o un-deg-tri o lyfrau Arithmetica Diophantus wedi goroesi mewn Groeg ac mae pedwar arall wedi goroesi mewn cyfieithiad Arabeg. Mae'r Arithmetica yn gasgliad o broblemau sydd wedi'u cwblhau, lle mae'r dasg yn ddieithriad i ddod o hyd i atebion rhesymegol i system o hafaliadau polynomial, fel arfer o'r ffurf $f(x,y)=z^2$ neu $f(x,y,z)=w^2$. Felly, y dyddiau hyn, rydym yn siarad am hafaliadau Diophantine pan fyddwn yn siarad am hafaliadau polynomial y mae'n rhaid dod o hyd i atebion rhesymegol neu gyfanrif iddynt.

Gellir dweud bod Diophantus yn astudio pwyntiau rhesymegol, hynny yw, pwyntiau y mae eu cyfesurynnau'n rhesymol - ar gromliniau ac amrywiadau algebraidd; fodd bynnag, yn wahanol i Roegiaid y cyfnod Clasurol, a wnaeth yr hyn y byddem bellach yn ei alw'n algebra sylfaenol mewn termau geometregol, gwnaeth Diophantus yr hyn y byddem ni nawr yn ei alw'n 'geometreg algebraidd sylfaenol' mewn termau algebraidd yn unig. Mewn iaith fodern, yr hyn a wnaeth Diophantus oedd hyn: o ystyried hafaliad o'r ffurf (dyweder) $f(x_1,x_2,x_3)=0$, ei nod oedd dod o hyd i dair swyddogaeth resymegol $g_1,g_2,g_3$ fel bod, ar gyfer holl werthoedd $r$ a $s$, gosod $x_i=g_i(r,s)$ ar gyfer $i=1,2,3$ sy'n rhoi ateb i $f(x_1,x_2,x_3)=0.$

Astudiodd Diophantus hefyd hafaliadau rhai cromliniau nad ydynt yn rhesymol, nad oes unrhyw barametrisiad rhesymegol yn bosibl ar eu cyfer. Llwyddodd i ddod o hyd i rai pwyntiau rhesymegol ar y cromliniau hyn (cromliniau eliptig, fel mae'n digwydd, yn yr hyn sy'n ymddangos fel y tro cyntaf) trwy'r hyn sy'n gyfystyr ag adeiladwaith tangiad: wedi'i drosi'n geometreg gyfesurynnol. Byddai ei ddull yn cael ei ddelweddu fel lluniadu tangiad i gromlin ar bwynt rhesymegol hysbys, ac yna'n darganfod pwynt croestoriad arall y tangiad â'r gromlin; mae'r pwynt arall hwnnw'n bwynt rhesymegol newydd.

Er bod Diophantus yn ymwneud i raddau helaeth ag atebion rhesymegol, cymerodd rai canlyniadau ar gyfanrifau, yn benodol bod pob cyfanrif yn gyfanswm o bedwar sgwâr.

Āryabhaṭa, Brahmagupta, Bhāskara

Er bod seryddiaeth Gwlad Groeg yn ôl pob tebyg wedi dylanwadu ar ddysgu Indiaidd, hyd at gyflwyno trigonometreg,Nodyn:Sfn ymddengys ei bod yn wir bod mathemateg Indiaidd yn draddodiad brodorol fel arall; yn benodol, nid oes tystiolaeth bod Elfennau Euclid wedi cyrraedd India cyn y 18g.Nodyn:Sfn

Dangosodd Āryabhaṭa (476-550 OC) fod parau o gyfuniadau ar yr un pryd $n\equiv a_1{modm}_1$, $n\equiv a_2{modm}_2$ y gellid ei ddatrys trwy ddull o'r enw kuṭṭaka, neu pulveriser; mae hon yn weithdrefn sy'n agos at yr algorithm Ewclidaidd, a ddarganfuwyd yn ôl pob tebyg yn annibynnol yn India.Nodyn:Sfn Mae'n ymddangos bod Āryabhaṭa wedi ystyried cymwysiadau i gyfrifiadau seryddol.Nodyn:Sfn

Dechreuodd Brahmagupta (628 OC) yr astudiaeth systematig o hafaliadau cwadratig amhenodol - yn enwedig hafaliad Pell, sydd wedi'i gam-enwi, y gallai fod gan Archimedes ddiddordeb ynddo gyntaf, ac na ddechreuwyd ei ddatrys yn y Gorllewin tan amser Fermat ac Euler. Yn ddiweddarach, byddai awduron Sansgrit yn dilyn, gan ddefnyddio terminoleg dechnegol Brahmagupta. Daethpwyd o hyd i weithdrefn gyffredinol (y chakravala, neu'r "dull cylchol") ar gyfer datrys hafaliad Pell o'r diwedd gan Jayadeva (a ddyfynnwyd yn yr 11g; ond collwyd ei waith, ers hynny); mae'r dangosiad cynharaf sydd wedi goroesi yn ymddangos yn Bīja-gaṇita Bhāskara II (12g).Nodyn:Sfn

Arhosodd mathemateg Indiaidd yn anhysbys i raddau helaeth yn Ewrop tan ddiwedd y 12g. Nodyn:Sfn Cyfieithwyd gwaith Brahmagupta a Bhāskara i'r Saesneg ym 1817 gan Henry Colebrooke.Nodyn:Sfn

Rhifyddeg yn yr oes aur Islamaidd

Yn gynnar yn y nawfed ganrif, gorchmynnodd y caliph Al-Ma'mun gyfieithiadau o lawer o weithiau mathemategol Gwlad Groeg ac o leiaf un gwaith Sansgrit (y Sindhind, a all fod yn waith gan Brahmagupta). Cyfieithwyd prif waith Diophantus, yr Arithmetica, i'r Arabeg gan Qusta ibn Luqa (820–912). Mae rhan o'r traethawd al-Fakhri (gan al-Karajī, 953 - ca. 1029) yn adeiladu arno i raddau. Yn ôl Rashed Roshdi, roedd Ibn al-Haytham cyfoeswr i Al-Karajī yn gwybod Nodyn:Sfn beth fyddai’n cael ei alw’n 'theorem Wilson' yn ddiweddarach.

Gorllewin Ewrop yn yr Oesoedd Canol

Heblaw am draethawd ar sgwariau mewn dilyniant rhifyddeg gan Fibonacci - a deithiodd ac a astudiodd yng ngogledd Affrica a Chaercystennin - ni wnaed unrhyw theori rhif gwerth ei halen yng ngorllewin Ewrop yn ystod yr Oesoedd Canol. Dechreuodd materion newid yn Ewrop ddiwedd y Dadeni, diolch i astudiaeth o'r newydd o weithiau hynafiaeth Gwlad Groeg. Y catalydd i hyn oedd y cyfieithiad i'r Lladin o Arithmetica gan Diophantus.

Damcaniaeth rhif modern cynnar

Fermat

Ni chyhoeddodd Pierre de Fermat (1607–1665) ei ysgrifau erioed; yn benodol, mae ei waith ar theori rhif wedi'i gynnwys bron yn gyfan gwbl mewn llythyrau at fathemategwyr ac mewn nodiadau ymylol preifat.Nodyn:Sfn

Gwnaeth Fermat y cyfraniadau canlynol i'r maes:

• Un o ddiddordebau cyntaf Fermat oedd rhifau perffaith (sy'n ymddangos yn Euclid, Elfennau IX) a rhifau cyfeillgar (amicable numbers); arweiniodd y pynciau hyn at weithio ar rannwyr cyfanrif (integer divisors), a oedd o'r dechrau ymhlith pynciau'r ohebiaeth (1636 ymlaen) a'i rhoddodd mewn cysylltiad â chymuned fathemategol y dydd.
• Yn 1638, honnodd Fermat, heb brawf, y gellir mynegi'r holl rifau cyfan fel swm pedwar sgwâr neu lai.
• Theorem Bychan Fermat (1640): os nad yw a yn rhanadwy gan rif cysefin p, yna $a^{p-1}\equiv 1modp.$
• Os yw a a b yn coprime, yna nid yw $a^2+b^2$ yn rhanadwy gan unrhyw prime congruent â −1 modulo 4; a gellir ysgrifennu pob rhif cysefin i 1 modwlws 4 ar y ffurf $a^2+b^2$.Nodyn:Sfn Mae'r ddau ddatganiad hyn hefyd yn dyddio o 1640; ym 1659, nododd Fermat wrth Huygens ei fod wedi profi'r datganiad olaf trwy'r dull o ddisgyniad anfeidrol (the method of infinite descent).Nodyn:Sfn
• Yn 1657, cododd Fermat y broblem o ddatrys $x^2-N{y}^2=1$ fel her i fathemategwyr Saesneg. Datryswyd y broblem mewn ychydig fisoedd gan Wallis a Brouncker. Nodyn:Sfn Ystyriodd Fermat bod eu datrysiad yn ddilys, ond nododd eu bod wedi darparu algorithm heb brawf (fel yr oedd Jayadeva a Bhaskara, er nad oedd Fermat yn ymwybodol o hyn). Dywedodd y gallai prawf ddod o hyd i ddisgyniad anfeidrol.
• Nododd a phrofodd Fermat (yn ôl disgyniad anfeidrol) yn yr atodiad i Sylwadau ar Diophantus (Ars. XLV) Nodyn:Sfn nad oes gan $x^4+y^4=z^4$ atebion dibwys yn y cyfanrifau. Soniodd Fermat hefyd wrth ei ohebwyr hefyd nad oes gan $x^3+y^3=z^3$ atebion dibwys, ac y gallai hyn hefyd gael ei brofi gan ddisgyniad anfeidrol.Nodyn:Sfn Mae'r prawf cyntaf y gwyddys amdano oherwydd Euler (1753; yn wir o ddisgyniad anfeidrol).Nodyn:Sfn
• Honnodd Fermat (Theorem Olaf Fermat) ei fod wedi dangos nad oes unrhyw atebion i $x^n+y^n=z^n$ i'r cyfan o $n\ge 3$ ; mae'r honiad hwn yn ymddangos yn ei anodiadau ar gyrion ei gopi o Diophantus.

Euler

Leonhard Euler

Sbardunwyd diddordeb Leonhard Euler (1707–1783) mewn theori rhif gyntaf ym 1729, pan gyfeiriodd ffrind iddo, Goldbach, tuag at rywfaint o waith Fermat ar y pwnc.Nodyn:SfnNodyn:Sfn Galwyd hyn yn "aileni" theori rhif modern,Nodyn:Sfn oherwydd diffyg llwyddiant cymharol Fermat i ddenu ei gyfoeswyr at y pwnc.

Meysydd

Gellir dosbarthu damcaniaeth rhifau yn sawl is-faes, yn ôl y dulliau a ddefnyddir a'r math o gwestiynau sy'n cael eu hymchwilio:

Damcaniaeth elfennol rhifau

Astudiaeth o'r cyfanrifau heb ddefnyddio dulliau o ganghennau eraill o fathemateg. Dyma rhai o'r pethau a astudir:

• Cwestiynau rhaniadwyedd
• Defnydd o'r Algorithm Ewclidaidd
• Canfod ffactorau cysefin
• Rhifau perffaith
• Rhifyddeg modylol
• Priodweddau ffwythiant Möbius a'r ffwythiant φ
• Dilyniannau cyfanrifol
• Y ffwythiant ffactorial "!"
• Rhifau Fibonacci

Er ei fod yn bosib mynegi rhai o broblemau mawr damcaniaeth rhifau o fewn damcaniaeth rhifau elfennol, yn aml mae angen dulliau a dealltwriaeth dwfn o feysydd eraill i'w datrys. Mae theorem olaf Fermat yn enghraifft o hyn.

Mae'r term elfennol yn gyffredinol yn dynodi dull nad yw'n defnyddio dadansoddiad cymhlyg. Er enghraifft, profwyd y theorem rhif cysefin gyntaf gan ddefnyddio dadansoddiad cymhlyg ym 1896, ond, ym 1949 gan Erdős a Selberg y canfuwyd prawf elfennol cyntaf.Nodyn:Sfn Mae'r term ychydig yn amwys: er enghraifft, mae proflenni sy'n seiliedig ar theoremau Tauberiaidd cymhlyg (er enghraifft, Wiener-Ikehara) yn aml yn cael eu hystyried yn eithaf goleuedig ond nid yn elfennol, er gwaethaf defnyddio dadansoddiad Fourier, yn hytrach na dadansoddiad cymhlyg fel y cyfryw. Yma fel mewn mannau eraill, gall prawf elfennol fod yn hirach ac yn anoddach i'r mwyafrif o ddarllenwyr nag un nad yw'n elfennol.

Damcaniaethwyr rhif Paul Erdős a Terence Tao ym 1985, pan oedd Erdős yn 72 a Tao yn 10 oed.

Mae gan damcaniaeth rhif enw da o fod yn faes y gellir nodi llawer o'i ganlyniadau i'r lleygwr. Ar yr un pryd, nid yw proflenni'r canlyniadau hyn yn arbennig o hygyrch, yn rhannol oherwydd bod yr ystod o offer y maent yn eu defnyddio, os rhywbeth, yn anarferol o eang o fewn mathemateg.

Damcaniaeth rhif dadansoddol

Ffwythiant Riemann zeta ζ ( s ) yn yr plân cymhlyg. Mae lliw pwynt s yn rhoi gwerth ζ ( s ): mae lliwiau tywyll yn dynodi gwerthoedd sy'n agos at sero ac mae lliw yn rhoi dadl y gwerth.

Gellir diffinio theori rhifau dadansoddol

• o ran ei offer, fel astudiaeth o'r cyfanrifau trwy offer o ddadansoddiad real a chymhlyg;Nodyn:Sfn neu
• o ran ei bryderon, fel yr astudiaeth o fewn theori rhif amcangyfrifon ar faint a dwysedd, yn hytrach nag unfathiant.

Mae rhai pynciau yr ystyrir yn gyffredinol eu bod yn rhan o theori rhifau dadansoddol, er enghraifft, theori gogr, yn cael eu cynnwys yn well gan yr ail yn hytrach na'r diffiniad cyntaf: er enghraifft, ychydig o ddadansoddiad y mae rhai o theori rhidyll yn ei ddefnyddio, ac eto mae'n perthyn i theori rhifau dadansoddol.

Mae damcaniaeth dadansoddol rhifau yn defnyddio dulliau o galcwlws a dadansoddi cymhlyg i ymafael â phroblemau sy'n ymwneud a'r cyfanrifau.

Damcaniaeth algebreaidd rhifau

Yn y maes hwn, estynnir y cysyniad o rif i gynnwys rhifau algebreaidd, sef gwreiddiau polynomialau sydd â chyfernodau cyfanrifol. Ceir rhifau algebreaidd sy'n ymddwyn yn debyg i gyfanrifau, y cyfanrifau algebreaidd.

Damcaniaeth rhifau gyfrifiadurol

Gellir defnyddio algorithmau cyfrifiadurol perthnasol i gynorthwyo astudiaeth o damcaniaeth rhifau. Ceir cymhwysiad pwysig o rhai algorithmau wrth ceisio creu a thorri codau, algorithmau chwim i brofi rhifau cysefin a ffactori rhifau mawr er enghraifft.

Damcaniaeth rhif cyfrifiadol

Enghraifft gynnar yw'r hyn a alwn yn awr yn algorithm Ewclidaidd. Yn ei ffurf sylfaenol (sef, fel algorithm ar gyfer cyfrifiadura'r rhannydd cyffredin mwyaf) mae'n ymddangos fel Cynnig 2, Llyfr VII yn yr Elfennau, ynghyd â phrawf o gywirdeb. Fodd bynnag, yn y ffurf a ddefnyddir yn aml mewn theori rhif (sef, fel algorithm ar gyfer dod o hyd i atebion cyfanrif i hafaliad $ax+by=c$, neu, yr un peth, ar gyfer dod o hyd i'r meintiau y mae theorem gweddill Tsieineaidd yn sicrhau eu bodolaeth) mae'n ymddangos gyntaf yng ngweithiau Āryabhaṭa (CE 5ed-6ed ganrif) fel algorithm o'r enw kuṭṭaka ("pulveriser"), heb brawf o gywirdeb.

Rhidyll Lehmer, cyfrifiadur digidol cyntefig a ddefnyddir i ddod o hyd i gyfnodau a datrys hafaliadau Diophantine syml.

Er bod y gair algorithm yn mynd yn ôl i'r al-Khwārizmī mae disgrifiadau gofalus o ddulliau datrys yn hŷn na'r profion: mae dulliau o'r fath (hynny yw, algorithmau) mor hen ag unrhyw fathemateg rydym yn ei adnabod — yr hen Aifft, Babilon, Vedic, Tsieina — ond ymddangosodd y prawf / profion yn y cyfnod clasurol.

Achos cynnar o hyn yw'r hyn a alwn yn awr yn algorithm Ewclidaidd. Yn ei ffurf sylfaenol (sef, fel algorithm ar gyfer cyfrifiannu'r rhannydd cyffredin mwyaf) mae'n ymddangos fel Cynnig 2 Llyfr VII yr Elfennau, ynghyd â phrawf o gywirdeb. Fodd bynnag, yn y ffurf a ddefnyddir yn aml mewn theori rhif (sef, fel algorithm ar gyfer dod o hyd i atebion cyfanrif i hafaliad $ax+by=c$, neu, beth sydd yr un peth, ar gyfer darganfod y meintiau y mae theorem 'gweddill' Tsieineaidd yn sicrhau eu bodolaeth) mae'n ymddangos gyntaf yng ngweithiau Āryabhaṭa (5–6g) fel algorithm o'r enw kuṭṭaka ("pulveriser"), heb brawf o gywirdeb.

Mae dau brif gwestiwn: "A allwn ni gyfrifo hyn?" ac "A allwn ei gyfrifo'n gyflym?" Gall unrhyw un brofi a yw rhif yn gysefin neu, os nad ydyw, ei rannu'n ffactorau cysefin; mae gwneud hynny'n gyflym yn fater arall. Rydym bellach yn deall algorithmau cyflym ar gyfer profi <i>primality</i>, ond, er gwaethaf llawer o waith (damcaniaethol ac ymarferol), nid oes algorithm gwirioneddol gyflym ar gyfer ffactoreiddio.

Gall anhawster cyfrifiant fod yn ddefnyddiol: mae protocolau modern ar gyfer amgryptio negeseuon (er enghraifft, RSA) yn dibynnu ar swyddogaethau sy'n hysbys i bawb, ond y mae eu gwrthdroadau yn hysbys i ychydig yn unig, a byddent yn cymryd gormod o amser rhy hir i'w datrus ar eich pen eich hun. Er bod llawer o broblemau cyfrifiadol anodd y tu allan i theori rhif yn hysbys, mae'r mwyafrif o brotocolau amgryptio sy'n gweithio y dyddiau hyn yn seiliedig ar anhawster llond dwrn yn unig o broblemau damcaniaethol rhif.

Ffynonellau

• Nodyn:Cite book
• Nodyn:Cite journal (Subscription needed)
• Nodyn:Cite journal
• Nodyn:Cite book 1968 edition at archive.org
• Nodyn:Cite book
• Nodyn:Cite book
• Nodyn:Cite book
• Nodyn:Cite journal
• Nodyn:Cite book
• Nodyn:Cite book
• Nodyn:Cite journal
• Nodyn:Cite book
• Nodyn:Cite book
• Nodyn:Cite web
• Nodyn:Cite book
• Nodyn:Cite book
• Nodyn:Cite book
• Nodyn:Cite book
• Nodyn:Cite book
• Nodyn:Cite book
• Nodyn:Cite book
• Nodyn:Cite encyclopedia
• Nodyn:Cite book
• Nodyn:Cite book
• Nodyn:Cite book
• Nodyn:Cite book
• Nodyn:Cite book
• Nodyn:Cite web
• Nodyn:Cite book
• Nodyn:Cite book
• Nodyn:Cite journal
• Nodyn:Cite book
• Nodyn:Cite book
• Nodyn:Cite web
• Nodyn:Cite journal
• Nodyn:Cite journal
• Nodyn:Cite book
• Nodyn:Cite book
• Nodyn:Cite journal
• Nodyn:Cite journal
• Nodyn:Cite book
• Nodyn:Cite book
• Nodyn:Cite book
• Nodyn:Cite book Volume 1 Volume 2 Volume 3 Volume 4 (1912)
• Nodyn:Cite book For other editions, see Iamblichus#List of editions and translations
• Nodyn:Cite book This Google books preview of Elements of algebra lacks Truesdell's intro, which is reprinted (slightly abridged) in the following book:
• Nodyn:Cite book
• Nodyn:Cite book
• Nodyn:Cite journal
• Nodyn:Cite book
• Nodyn:Cite book

• Nodyn:Cite book
• Nodyn:Cite book