Primeca provo de Fermat

La primeca provo de Fermat estas probableca provo por kontroli ĉu entjero estas verŝajna primo.

Koncepto

Malgranda teoremo de Fermat diras ke se p estas primo kaj a estas interprimo al p, 1≤a<p, do ap-1-1 estas dividebla per p aŭ per la alia skribmaniero

Se oni bezonas provi ĉu p estas primo, tiam oni povas preni hazardajn a en la intervalo kaj konroli ĉu la egaleco veras. Se la egaleco ne veras por iu a, tiam p estas ne primo. Se la egaleco veras por multaj valoroj de a, tiam oni povas diri ke p estas verŝajna primo, aŭ pseŭdoprimo.

Povas okazi en la testoj ke oni ne prenis iun a tian ke la egaleco malveras. Ĉiu a tia ke

kiam n estas komponigita estas sciata kiel neatestanto de Fermat. Se a estas tia ke

tiam a estas atestanto de Fermat por la komponigiteco de n.