Reciproka primeco

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

Ekzemple, 12 kaj 55 estas interprimoj, sed 12 kaj 33 estas ne interprimoj ĉar ili estas ambaŭ divideblaj per 3. Nombro 1 estas interprimo al ĉiu entjero.

Rapida maniero por kontroli ĉu du nombroj estas interprimoj estas per kalkulado de ilia plej granda komuna divizoro, ekzemple per 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 kvanto de entjeroj inter 1 kaj n kiuj estas interprimoj al n.

Propraĵoj

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

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

Du entjeroj a kaj b estas interprimoj 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 interprimoj 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 interprimoj 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 interprimoj se kaj nur se en karteziaj koordinato rekta streko (a, b)-(0, 0) ne trapasas la aliajn punktojn kun ambaŭ entjeraj koordinatoj.

Du entjeroj a kaj b estas interprimoj se kaj nur se nombroj 2^a-1 kaj 2^b-1 estas interprimoj.

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

Se a kaj b estas interprimo 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 b aŭ p dividas na c.

Probablo de interprimeco

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

Pruvo

a kaj b estas interprimoj 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/p², kaj la probablo ke almenaŭ unu el ili ne estas dividebla je p estas 1-1/p². Tial la probablo ke du nombroj estas interprimoj estas donita per produto tra ĉiuj primoj,

$\prod _{p}^{\infty }\left(1-{\frac {1}{p^{2}}}\right)=\left(\prod _{p}^{\infty }{\frac {1}{1-p^{-2}}}\right)^{-1}={\frac {1}{\zeta (2)}}={\frac {6}{\pi ^{2}}}.$

Ĉ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 π²/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 inter si interprimoj 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 interprimoj. Ĉi tiu probablo ne estas akurate 6/(π²), sed en la limigo kun $N\to \infty$ estas $P(N)\to 6/\pi ^{2}$.

Vidu ankaŭ

• Primo
• Eŭlera φ funkcio