Reciproka primeco

El Vikipedio, la libera enciklopedio
(Alidirektita el Interprimo)

En matematiko, pozitivaj entjeroj a kaj b estas reciproke primaj, se ili ne havas komunajn divizorojn escepte de 1, aŭ, ekvivalente, se ilia plej granda komuna divizoro estas 1.

Ekzemple, 12 kaj 55 estas reciproke primaj, sed 12 kaj 33 ne estas reciproke primaj, ĉar ili ambaŭ estas divideblaj per 3. Nombro 1 estas reciproke prima kun ĉiu entjero.

Kontroli, ĉu du nombroj estas reciproke primaj, oni povas per kalkulado de ilia plej granda komuna divizoro, ekzemple, pere de la eŭklida algoritmo. Prima faktorigo (por posta komparo de la faktoroj) estas multe pli malrapida por grandaj nombroj.

Eŭlera φ-funkcio de pozitiva entjero n estas la nombro de entjeroj inter 1 kaj n, kiuj estas reciproke primaj kun n.

Ecoj[redakti | redakti fonton]

Nombroj 4 kaj 9 estas reciproke primaj ĉar la diagonalo ne sekcas la aliajn kradajn punktojn

Estas kondiĉoj kiuj estas ekvivalentaj al tio ke a kaj b estas reciproke primaj.

Du entjeroj a kaj b estas reciproke primaj se kaj nur se ekzistas entjeroj x kaj y tiaj ke ax+by=1 (vidu en idento de Bézout).

Du entjeroj a kaj b estas reciproke primaj, se kaj nur se b havas inverson module a, do se ekzistas entjero y tia ke by ≡ 1 (mod a). En aliaj vortoj, b estas unuo en la ringo Z/aZ de entjeroj module a.

Sekve de tio, se a kaj b estas reciproke primaj kaj br ≡ bs (mod a), tiam r ≡ s (mod a) (ĉar oni povas "dividi per b" laborante module a).

Du entjeroj a kaj b estas reciproke primaj se kaj nur se en kartezia koordinato rekta streko (a, b)-(0, 0) ne trapasas la aliajn punktojn kun ambaŭ entjeraj koordinatoj.

Du entjeroj a kaj b estas reciproke primaj, se kaj nur se nombroj 2a-1 kaj 2b-1 estas reciproke primaj.

Se a kaj b estas reciproke primaj, kaj a kaj c estas reciproke primaj, tiam a kaj bc estas ankaŭ reciproke primaj, ĉar bc havas nur primajn faktorojn de b kaj c, kaj neniu el tiuj estas primaj faktoroj de a.

Se a kaj b estas reciproke primaj kaj a dividas produton bc, tiam a dividas na c. Ĉi tio povas esti vidita kiel ĝeneraligo de eŭklida lemo, kiu diras ke se p estas primo, kaj p dividas produton bc, tiam p dividas na bp dividas na c.

Probablo de interprimeco[redakti | redakti fonton]

La probablo ke du hazarde elektitaj entjeroj a kaj b estas reciproke primaj estas 6/(π2)≈0,6.

Pruvo

a kaj b estas reciproke primaj se kaj nur se ne ekzistas primo kiu dividas ambaŭ ilin.

Probablo ke nombro estas dividebla per primo (aŭ iu entjero) p estas 1/p. De ĉi tie probablo ke du nombroj estas ambaŭ divideblaj per ĉi tiu primo estas 1/p2, kaj la probablo ke almenaŭ unu el ili ne estas dividebla je p estas 1-1/p2. Tial la probablo ke du nombroj estas reciproke primaj estas donita per produto tra ĉiuj primoj,

Ĉi tie ζ estas la rimana ζ funkcio. La egaleco de la produto tra primoj al ζ(2) estas ekzemplo de eŭlera produto. Egaleco de ζ(2) al π2/6 estas la problemo de Basel, solvita de Leonhard Euler en 1735.

Pli ĝenerale, la probablo de tio ke k hazarde elektitaj entjeroj estas ĉiuj popare reciproke primaj estas 1/ζ(k).

Reale la entjeroj estas elektataj hazarde inter 1 kaj iu entjera supera baro N. Tiam por ĉiu N, estas probablo P(N), ke du tiel hazarde elektitaj nombroj estas reciproke primaj. Ĉi tiu probablo ne estas akurate 6/(π2), sed en la limigo kun estas .

Vidu ankaŭ[redakti | redakti fonton]