Damcaniaeth rhifau

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." Mae maes damcaniaethwyr rhif yn cynnwys rhifau cysefin, nodweddion gwrthrychau a wnaed o rifau cymarebol a chyfanrifau alegbraidd.

Damcaniaeth rhifau

Math o gyfrwng	maes o fewn mathemateg
Rhan o	mathemateg, Mathemateg bur
Yn cynnwys	elementary number theory
Ffeiliau perthnasol ar Gomin Wicimedia

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}}\left(x-{\frac {1}{x}}\right)\right)^{2}+1=\left({\frac {1}{2}}\left(x+{\frac {1}{x}}\right)\right)^{2},$

sy'n digwydd yn naturiol o fewn ymarferion yr Hen Fabiloniaid. 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.

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. 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). 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. 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. 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, 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.

Dangosodd Āryabhaṭa (476-550 OC) fod parau o gyfuniadau ar yr un pryd $n\equiv a_{1}{\bmod {m}}_{1}$, $n\equiv a_{2}{\bmod {m}}_{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. Mae'n ymddangos bod Āryabhaṭa wedi ystyried cymwysiadau i gyfrifiadau seryddol.

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).

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

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 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.

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 1{\bmod {p}}.$
• 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}$. 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).
• Yn 1657, cododd Fermat y broblem o ddatrys $x^{2}-Ny^{2}=1$ fel her i fathemategwyr Saesneg. Datryswyd y broblem mewn ychydig fisoedd gan Wallis a Brouncker. 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) 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. Mae'r prawf cyntaf y gwyddys amdano oherwydd Euler (1753; yn wir o ddisgyniad anfeidrol).
• 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\geq 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. Galwyd hyn yn "aileni" theori rhif modern, 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. 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; 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

• Apostol, Tom M. (1976). Introduction to analytic number theory. Undergraduate Texts in Mathematics. Springer. ISBN 978-0-387-90163-3. Cyrchwyd 2016-02-28.
• Apostol, Tom M. (n.d.). An Introduction to the Theory of Numbers. (Review of Hardy & Wright.) Mathematical Reviews (MathSciNet). American Mathematical Society. MR 0568909. https://www.ams.org/mathscinet/. Adalwyd 2016-02-28. (Subscription needed)
• Becker, Oskar (1936). "Die Lehre von Geraden und Ungeraden im neunten Buch der euklidischen Elemente" (yn de). Quellen und Studien zur Geschichte der Mathematik, Astronomie und Physik. Abteilung B:Studien 3: 533–53.
• Boyer, Carl Benjamin; Merzbach, Uta C. (1991) [1968]. A History of Mathematics (arg. 2nd). New York: Wiley. ISBN 978-0-471-54397-8. 1968 edition at archive.org
• Clark, Walter Eugene (trans.) (1930). The Āryabhaṭīya of Āryabhaṭa: An ancient Indian work on Mathematics and Astronomy. University of Chicago Press. Cyrchwyd 2016-02-28.
• Colebrooke, Henry Thomas (1817). Algebra, with Arithmetic and Mensuration, from the Sanscrit of Brahmegupta and Bháscara. London: J. Murray. Cyrchwyd 2016-02-28.
• Davenport, Harold; Montgomery, Hugh L. (2000). Multiplicative Number Theory. Graduate texts in mathematics. 74 (arg. revised 3rd). Springer. ISBN 978-0-387-95097-6.
• Edwards, Harold M. (November 1983). "Euler and Quadratic Reciprocity". Mathematics Magazine 56 (5): 285–91. doi:10.2307/2690368. JSTOR 2690368. https://archive.org/details/sim_mathematics-magazine_1983-11_56_5/page/285.
• Edwards, Harold M. (2000) [1977]. Fermat's Last Theorem: a Genetic Introduction to Algebraic Number Theory. Graduate Texts in Mathematics. 50 (arg. reprint of 1977). Springer Verlag. ISBN 978-0-387-95002-0.
• Fermat, Pierre de (1679). Varia Opera Mathematica (yn Ffrangeg a Lladin). Toulouse: Joannis Pech. Cyrchwyd 2016-02-28.
• Friberg, Jöran (August 1981). "Methods and Traditions of Babylonian Mathematics: Plimpton 322, Pythagorean Triples and the Babylonian Triangle Parameter Equations". Historia Mathematica 8 (3): 277–318. doi:10.1016/0315-0860(81)90069-0.
• von Fritz, Kurt (2004). "The Discovery of Incommensurability by Hippasus of Metapontum". In Christianidis, J. (gol.). Classics in the History of Greek Mathematics. Berlin: Kluwer (Springer). ISBN 978-1-4020-0081-2.
• Gauss, Carl Friedrich; Waterhouse, William C. (trans.) (1966) [1801]. Disquisitiones Arithmeticae. Springer. ISBN 978-0-387-96254-2.
• Goldfeld, Dorian M. (2003). "Elementary Proof of the Prime Number Theorem: a Historical Perspective" (PDF). Cyrchwyd 2016-02-28.
• Goldstein, Catherine; Schappacher, Norbert (2007). "A book in search of a discipline". In Goldstein, C.; Schappacher, N.; Schwermer, Joachim (gol.). The Shaping of Arithmetic after C.F. Gauss's "Disquisitiones Arithmeticae". Berlin & Heidelberg: Springer. tt. 3–66. ISBN 978-3-540-20441-1.
• Granville, Andrew (2008). "Analytic number theory". In Gowers, Timothy; Barrow-Green, June; Leader, Imre (gol.). The Princeton Companion to Mathematics. Princeton University Press. ISBN 978-0-691-11880-2. Cyrchwyd 2016-02-28.
• Porphyry; Guthrie, K.S. (trans.) (1920). Life of Pythagoras. Alpine, New Jersey: Platonist Press.
• Guthrie, Kenneth Sylvan (1987). The Pythagorean Sourcebook and Library. Grand Rapids, Michigan: Phanes Press. ISBN 978-0-933999-51-0.
• Hardy, Godfrey Harold; Wright, E.M. (2008) [1938]. An Introduction to the Theory of Numbers (arg. Sixth). Oxford University Press. ISBN 978-0-19-921986-5. MR 2445243.
• Heath, Thomas L. (1921). A History of Greek Mathematics, Volume 1: From Thales to Euclid. Oxford: Clarendon Press. Cyrchwyd 2016-02-28.
• Hopkins, J.F.P. (1990). "Geographical and Navigational Literature". In Young, M.J.L.; Latham, J.D.; Serjeant, R.B. (gol.). Religion, Learning and Science in the 'Abbasid Period. The Cambridge history of Arabic literature. Cambridge University Press. ISBN 978-0-521-32763-3.
• Iwaniec, Henryk; Kowalski, Emmanuel (2004). Analytic Number Theory. American Mathematical Society Colloquium Publications. 53. Providence, RI: American Mathematical Society. ISBN 978-0-8218-3633-0.
• Plato; Jowett, Benjamin (trans.) (1871). Theaetetus. Archifwyd o'r gwreiddiol ar 2011-07-09. Cyrchwyd 2022-04-06.
• Lam, Lay Yong; Ang, Tian Se (2004). Fleeting Footsteps: Tracing the Conception of Arithmetic and Algebra in Ancient China (arg. revised). Singapore: World Scientific. ISBN 978-981-238-696-0. Cyrchwyd 2016-02-28.
• Long, Calvin T. (1972). Elementary Introduction to Number Theory (arg. 2nd). Lexington, VA: D.C. Heath and Company. LCCN 77171950.
• Mahoney, M.S. (1994). The Mathematical Career of Pierre de Fermat, 1601–1665 (arg. Reprint, 2nd). Princeton University Press. ISBN 978-0-691-03666-3. Cyrchwyd 2016-02-28.
• Milne, J. S. (18 March 2017). "Algebraic Number Theory". Cyrchwyd 7 April 2020.
• Montgomery, Hugh L.; Vaughan, Robert C. (2007). Multiplicative Number Theory: I, Classical Theory. Cambridge University Press. ISBN 978-0-521-84903-6. Cyrchwyd 2016-02-28.
• Morrow, Glenn Raymond (trans., ed.); Proclus (1992). A Commentary on Book 1 of Euclid's Elements. Princeton University Press. ISBN 978-0-691-02090-7.
• Mumford, David (March 2010). "Mathematics in India: reviewed by David Mumford". Notices of the American Mathematical Society 57 (3): 387. ISSN 1088-9477. https://www.ams.org/notices/201003/rtx100300385p.pdf.
• Neugebauer, Otto E. (1969). The Exact Sciences in Antiquity. 9 (arg. corrected reprint of the 1957). New York: Dover Publications. tt. 1–191. ISBN 978-0-486-22332-2. PMID 14884919. Cyrchwyd 2016-03-02.
• Neugebauer, Otto E.; Sachs, Abraham Joseph; Götze, Albrecht (1945). Mathematical Cuneiform Texts. American Oriental Series. 29. American Oriental Society etc.
• O'Grady, Patricia (September 2004). "Thales of Miletus". The Internet Encyclopaedia of Philosophy. Cyrchwyd 7 February 2012.
• Pingree, David; Ya'qub, ibn Tariq (1968). "The Fragments of the Works of Ya'qub ibn Tariq". Journal of Near Eastern Studies 26.
• Pingree, D.; al-Fazari (1970). "The Fragments of the Works of al-Fazari". Journal of Near Eastern Studies 28.
• Plofker, Kim (2008). Mathematics in India. Princeton University Press. ISBN 978-0-691-12067-6.
• Qian, Baocong, gol. (1963). Suanjing shi shu (Ten Mathematical Classics) (yn Tsieinëeg). Beijing: Zhonghua shuju. Cyrchwyd 2016-02-28.
• Rashed, Roshdi (1980). "Ibn al-Haytham et le théorème de Wilson". Archive for History of Exact Sciences 22 (4): 305–21. doi:10.1007/BF00717654. https://archive.org/details/sim_archive-for-history-of-exact-sciences_1980_22_4/page/305.
• Robson, Eleanor (2001). "Neither Sherlock Holmes nor Babylon: a Reassessment of Plimpton 322". Historia Mathematica 28 (3): 167–206. doi:10.1006/hmat.2001.2317. http://www.hps.cam.ac.uk/people/robson/neither-sherlock.pdf.
• Sachau, Eduard; Bīrūni, ̄Muḥammad ibn Aḥmad (1888). Alberuni's India: An Account of the Religion, Philosophy, Literature, Geography, Chronology, Astronomy and Astrology of India, Vol. 1. London: Kegan, Paul, Trench, Trübner & Co. Cyrchwyd 2016-02-28.
• Serre, Jean-Pierre (1996) [1973]. A Course in Arithmetic. Graduate texts in mathematics. 7. Springer. ISBN 978-0-387-90040-7.
• Smith, D.E. (1958). History of Mathematics, Vol I. New York: Dover Publications.
• Tannery, Paul; Henry, Charles (eds.); Fermat, Pierre de (1891). Oeuvres de Fermat. (4 Vols.) (yn Ffrangeg a Lladin). Paris: Imprimerie Gauthier-Villars et Fils.CS1 maint: extra text: authors list (link) Volume 1 Volume 2 Volume 3 Volume 4 (1912)
• Iamblichus; Taylor, Thomas (trans.) (1818). Life of Pythagoras or, Pythagoric Life. London: J.M. Watkins. Archifwyd o'r gwreiddiol ar 2011-07-21. Cyrchwyd 2022-04-06. For other editions, see Iamblichus#List of editions and translations
• Truesdell, C.A. (1984). "Leonard Euler, Supreme Geometer". In Hewlett, John (trans.) (gol.). Leonard Euler, Elements of Algebra (arg. reprint of 1840 5th). New York: Springer-Verlag. ISBN 978-0-387-96014-2. This Google books preview of Elements of algebra lacks Truesdell's intro, which is reprinted (slightly abridged) in the following book:
• Truesdell, C.A. (2007). "Leonard Euler, Supreme Geometer". In Dunham, William (gol.). The Genius of Euler: reflections on his life and work. Volume 2 of MAA tercentenary Euler celebration. New York: Mathematical Association of America. ISBN 978-0-88385-558-4. Cyrchwyd 2016-02-28.
• Varadarajan, V.S. (2006). Euler Through Time: A New Look at Old Themes. American Mathematical Society. ISBN 978-0-8218-3580-7. Cyrchwyd 2016-02-28.
• Vardi, Ilan (April 1998). "Archimedes' Cattle Problem". American Mathematical Monthly 105 (4): 305–19. doi:10.2307/2589706. JSTOR 2589706. https://www.cs.drexel.edu/~crorres/Archimedes/Cattle/cattle_vardi.pdf.
• van der Waerden, Bartel L.; Dresden, Arnold (trans) (1961). Science Awakening. 1 or 2. New York: Oxford University Press.
• Weil, André (1984). Number Theory: an Approach Through History – from Hammurapi to Legendre. Boston: Birkhäuser. ISBN 978-0-8176-3141-3. Cyrchwyd 2016-02-28.

• G.H. Hardy; E.M. Wright (2008) [1938]. An introduction to the theory of numbers (arg. rev. by D.R. Heath-Brown and J.H. Silverman, 6th). Oxford University Press. ISBN 978-0-19-921986-5. Cyrchwyd 2016-03-02.
• Vinogradov, I.M. (2003) [1954]. Elements of Number Theory (arg. reprint of the 1954). Mineola, NY: Dover Publications.