Leama Euclid

In uimhirtheoiric, leama tábhachtach is ea leama Euclid, maidir le roinnteoirí príomha.

Is é ráiteas leama Euclid mar a leanas: bíodh slánuimhreacha iad a,b agus bíodh uimhir phríomha í p. Má $p\mid ab$, ansin $p\mid a$ or $p\mid b$. Úsáidtear an leama seo i gcruthúnas bunteoirim na huimhríochta.

Cruthúnas

Úsáideann an cruthúnas seo Leama Bézout. Bíodh $a,b$ ina slánuimhreacha nach bhfuil cothrom le 0, agus bíodh $d$ ina roinnteoir coiteann is airde an dá uimhir; ansin tá dhá shlánumhir $x,y$ ann go bhfuil ${\textstyle ax+by=d}$.

Glac leis gurb slánuimhreacha iad $a,b$, agus gurb uimhir phríomha í $p$, atá ina roinnteoir den uimhir $ab$. Má tá $a$ inroinnte ar $p$, níl a thuilleadh le cruthú. Dá bhrí sin, glac leis nach bhfuil $a$ inroinnte ar $p$. Mar sin is é 1 an roinnteoir coiteann is airde. De bharr Leama Bézout, tá dhá shlánuimhir $x,y$ go bhfuil $ax+py=1$. Iolraigh an dá taobh faoi $b$ chun $abx+pby=b$. Roinneann $p$ an tslánuimhir $ab$, mar sin roinneann $p$ an slonn $abx+pby$, agus dá bhrí sin tá $b$ inroinnte ar $p$ $\blacksquare$