Leama Euclid

Ón Vicipéid, an chiclipéid shaor.

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á , ansin or . Úsáidtear an leama seo i gcruthúnas bunteoirim na huimhríochta.

Cruthúnas[cuir in eagar | athraigh foinse]

Úsáideann an cruthúnas seo Leama Bézout. Bíodh ina slánuimhreacha nach bhfuil cothrom le 0, agus bíodh ina roinnteoir coiteann is airde an dá uimhir; ansin tá dhá shlánumhir ann go bhfuil .

Glac leis gurb slánuimhreacha iad , agus gurb uimhir phríomha í , atá ina roinnteoir den uimhir . Má tá inroinnte ar , níl a thuilleadh le cruthú. Dá bhrí sin, glac leis nach bhfuil inroinnte ar . Mar sin is é 1 an roinnteoir coiteann is airde. De bharr Leama Bézout, tá dhá shlánuimhir go bhfuil . Iolraigh an dá taobh faoi chun . Roinneann an tslánuimhir , mar sin roineann an slonn , agus dá bhrí sin tá inroinnte ar