Prostibrojevi

Prosti brojevi ili prim-brojevi su svi prirodni brojevi djeljivi bez ostatka samo s brojem 1 i sami sa sobom, a veći od broja 1. Prirodni brojevi koji su veći od broja 1, a nisu prosti brojevi nazivaju se složenim brojevima. Na primjer, 5 je prost broj jer je djeljiv samo s 1 i 5, a 6 je složen broj jer osim što je djeljiv s 1 i 6 dodatno može biti podjeljen s brojevima 2 i 3. Napomena: Broj 1 nije ni prost, ni složen.

Čemu prosti brojevi služe?

Prosti brojevi služe pri faktorizaciji, odnosno rastavljanju složenih brojeva na prim-faktore. Svaki složeni broj može se na jedinstven način rastaviti na prim-faktore.

Teorem(osnovni teorem aritmetike): Svaki se prirodan broj može prikazati kao produkt prostih faktora. Slijedi da se svaki prirodan broj n može zapisati u kanonskom obliku kao produkt potencija prostih brojeva. $$n = p_1^{\alpha_1}p_2^{\alpha_2}...p_k^{\alpha_k} $$ Faktorizacija na proste faktore je jedinstvena do na poredak faktora.

Primjer: Provjeravamo je li prirodan broj 30 prost:

In [108]:
from numba import jit
from math import sqrt
@jit
def je_li_prost(x):
    true = 1
    for i in xrange(2,int(sqrt(x)+1)):
        if(x % i == 0):
            true=0
            break
    if(true):
        return 1
    else:
        return 0
x=30
if(je_li_prost(x)==1):
    print('Broj {} je prost!'.format(x))
else:
    print('Broj {} nije prost!'.format(x))

Broj 30 nije prost!

Primjer rastava broja na proste faktore: $$30|2$$
$$15|3$$
$$5|5$$
$$1$$

$$30 = 2 * 3 * 5$$

Definicija:Najveći zajednički djelitelj dvaju brojeva je najveći broj kojim su djeljiva ta dva broja. Na isti se način definira i najveći zajednički djelitelj $nzd$ više brojeva.

Npr., najveći zajednički djelitelj brojeva 2 i 8 je:

In [35]:
from sympy import *
gcd(2,8)
Out[35]:
2

Pišemo:$$nzd(2, 8) = 2$$ ili ponekad pišemo $$M(2, 8) = 2 (mjera)$$.Primijetimo da je najveći zajednički djelitelj relativno prostih brojeva jednak 1 pa je $nzd(10,21)$ jednako:

In [34]:
gcd(10,21)
Out[34]:
1

Definicija: Najmanji zajednički višekratnik dvaju ili više brojeva je najmanji broj koji je djeljiv svim tim brojevima.

Tako je najmanji zajednički višekratnik $(nzv)$ brojeva 6 i 4 jednak:

In [36]:
lcm(6,4)
Out[36]:
12

Dakle: $$nzv(6, 4) = 12$$ ili ponekad kraće $$v(6, 4) = 12 (višekratnik).$$

Relativno prosti brojevi

Relativno prosti brojevi su prirodni brojevi koji nemaju zajedničkog djelitelja osim 1.

Primjer: Provjeravamo jesu li prirodni brojevi 48 i 57 relativno prosti:

In [107]:
@jit
def rel_prost(x,y):
    true=1
    if(x<y):
        for i in xrange(2,x+1):
            if((x%i == 0) & (y%i == 0)):
                true=0
                break
    else:
        for i in range(2,y+1):
            if(x%i == 0 & y%i == 0):
                true=0
                break
    return true
x=48
y=57
if(rel_prost(x,y)):
    print('Brojevi {} i {} su relativno prosti'.format(x,y))
else:
    print('Brojevi {} i {} nisu relativno prosti'.format(x,y))

Brojevi 48 i 57 nisu relativno prosti

EUKLIDOV ALGORITAM: Za prirodne brojeve a i b vrijedi: $$nzd(a, b) = nzd(a, a − b).$$

Koristeći Euklidov algoritam izračunajmo $nzd(32,48)$:

In [106]:
@jit
def nzd(x,y):
    while(x != y):
        if(x > y):
            x -= y
        else:
            y -= x
    return x
x=32
y=48
print('nzd({},{}) = {}'.format(x,y,nzd(x,y)))

nzd(32,48) = 16

Neka još neodgovorena pitanja o prostim brojevima su:

  1. Postoji li općenita formula koja izračunava $n$-ti prosti broj?
  2. Postoji li formula za izračunavanje $n$-tog prostog broja $p_n$?
  3. Postoji li formula za izračunavanje prvog sljedećeg prostog broja, $p_n+1$, nakon što je zadan prethodni prosti broj $p_n$?
  4. Koliko je prostih brojeva manjih od nekog zadanog broja $x \in\mathbb{Q}$?

Teorem: Postoji beskonačno mnogo prostih brojeva.

Najveći dosad pronađeni prosti broj je: $$2^{74.207.281}-1.$$

Taj broj ima nevjerovatnih 22.338.618 cifara i nemoguće ga je napisati u njegovom originalnom obliku. Međutim u sljedećem videu možete vidjeti knjigu koja se sastoji od svih cifara tog prostog broja:

In [68]:
from IPython.display import YouTubeVideo
YouTubeVideo('tlpYjrbujG0')
Out[68]:

Fermatovi brojevi

Definicija: Brojevi $f_n = 2^{2^n} + 1$ zovu se Fermatovi brojevi.

Napomena: Fermat je smatrao da su svi brojevi ovog oblika prosti. Zaista, $f_0 = 3,\,f_1 = 5,\,f_2 = 17,\, f_3 = 257,\,f_4 = 65537$ jesu prosti brojevi. No, $f_5 = 232 + 1$ nije prost jer $ 641 |\, f_5$. Postoji hipoteza koja kaže da je samo konačno mnogo Fermatovih brojeva koji su prosti.

Fermatov broj $F_n = 2^{2^n} + 1$ za $n ≥ 1$ može se geometrijski prikazati kao kvadrat s duljinom stranice $2^{2^{n−1}}$ uvećan za jedinični kvadrat. Zaista, $F_n = (2^{2^{n−1}})^2 + 1$.

In [81]:
from sympy import *
from sympy import init_printing
init_printing()
n = Symbol('n')
simplify((2**(2**(n-1)))**2+1)
Out[81]:
$$2^{2^{n}} + 1$$
In [71]:
from IPython.display import Image
Image(url='data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAOQAAADBCAMAAADo6Ow6AAABAlBMVEX////q6v7y8v7x8f7u7v7w8P7v7/7s7P5LS/92dv/AwP6Hh/+lpf7b2/6Wlv/MzP6ysv5OTv/5+f/S0v/Gxv5RUf9jY/9mZv+EhP9zc/9UVP+urv5gYP+Tk//m5v66uv6cnP+iov7f3/4/P//V1f40NP/r6+tHR/85Of9YWP/29vbg4OC7u/5qav+Ghv+kpP6tra3ExMRtbW3Ozs6NjY20tLScnJwmJiYAAAB/f///0dEsLP//xcWhoaESEv8hIf9bW1v/VFT/paVFRUV9fX1aWloAAP//hYX/amr/ISEYGBg6OjovLy//NDT/AAD/6+v/jIxqamr/YGD/2tr/QkL/rq7G2rYtAAALQklEQVR4nO2d+1+byBrGMVcwSILmRgLmKgQiMTEXzVq3VtNtu909Xbfn/P//yoEwzyTtoElabDTO84O+n28IL4/AMLyDjCBwcXG9VKX/UMVA6u8kUltX67HOCctOOmDiW7CrFiIrhNE1q28tlv1xGIVJ6TAW6LCA6ChDmYooX2dZrcqww2qNoFiiCFbPgzWR7TBzBNZGtkOpCZZXwEqRmNSSe4FiajwI0tkMZWIsCBL7SophOTnBMDlHWPpYJ+tLKftgBxphyUw2TdhRmWRLSgdpZDNItniRm+QmuUlukpt8tialw2Qg7zoZBP51EkwFy9djDKvJLJNrhMW96yRh3nWSRE1k86+ThLWRzb9OIptComiuk4mOBNHIVVlWqrBMt1lm65S1EFRKiDQLkerSbCIiS6PZCoiuItmTbvMgUFNEdDqlzEKUy7BMrh8wrC6DtW3CmpkcWBbZmtNTsH1ka2p5MJqtaUdzuMbSgWIqiRLZTBxMBNtXGJbKycnvWVLOpQjb0wmLe+ckWcuBBpbJgh2VyZpj0gFY3gDjDQ83yU1yky/UpERbzaXWlWk1PZMsy8mp71nKM0nYMVrXJG1dfZOEhbSucc8kbV2T0bau6eNACZVEe9keZWKCsFODZbnGHsMaObCmTljaOAVrI1u6l91DtjKY1CaL7e0jW1qPpMdzVdQDlU5KQVC0LZZVQlhBZZlaIKyod8CsCmUtRJaNyKaspSOi2UpvI+q7xgN5fdcg8PuuYCpYvs6yWjXGsGqNML/GQz70+q6ENZHN77sS1kY2v++KbAoYr/Fwk9wkN8lNcpNbNfkarpOJK7cUyD1BpFsss8USwyoqy9QKWKkDJtpAxRZhrqWD0WxuizKazY2mxqOhX7mnIsqXKRMR1QyWVRvHDGtUwZo6eqdGDayNbHvlPFh2CqYdgZ0i214kfdfwu5CwGg9zF5IKvwsBe/QuJKzG85R3Ia+h4eEmuUlu8nmZXLuCHta6rlVBT/5IBT3a1pUdC2nS0YmDY/GYsJzBMrnOsroMdqBjfUYO0dJYyD6TrallEdWiHQtJnEhaIKmDqCRSRj/VCxrDbPsxprXACjqQaxEmiSUwmk2yXLAiskU0qvUzfVeZ7bvK6LvGn1Hf9XU0PNwkN8lNcpPc5FOYfA3Puybe2pVA9gkitcUyMYRZVuURVgGzWyJQoUOZCkaz2Z0CGM1mRzSqFUsEihVIlDrKUKaSKLmvMCyek+MMk3Nge0XCYsp+kqy5iWyxzFEK2Xpg0gFhyTyyRVX+iH9/TibWPycZllo+J8HCz0kwek7GecPDTXKT3OQOmQyt8VBG6zkhT0kmw2s8hCWWn5IkdZ9EEzWe2FKNpwdGazypqJ+SLLWPArVFRDUJ0YF1QKJqhmHthsEyowGWtUnUzlQJOsq7YFINjGZru/tg1R5YNDWeVnkaqNfpBUFZq7DMtVlW0lmml8CmLTDbJawsiWAVDUwrIBIlRDRb7+R5P4OeZp9Bj696Bj3+NM+gv46Gh5vkJrlJbvIXmezuvklzfE5NPssaTzaKGo9zjyjxlv6HOf1fc6sTwloMU1uPMnHBLJFhHcpotlD2+1omncFk4jiD0fB6sETPnZ3ak+O+MJuY5p0zHHmG5/rG5E6ck4Ox0D8XhjOhPxac4Vy+SXz80k2Oz0fmPHg/FEYDYTRcOl7vd2NPOtddoX/h7zX/ZPRPy+vFZ+P7sbkLJrs3puDczBzBOzyHDy/2wk1eDgVnducM7u7PJ7tqUvDOOvO916Kapuk8vNTSMAFK/ansYphADBkmoGxpmEBcDBMkHx4m8Gs8GCbIhg0TkMVSmwwTjO+6qxZJF7P5QFkLUVVi2dmUYVnFYJmhgOUrYNMzoFoJTKqCVTWwUg1MRrZsYZXJ7vuVHoWEZUAdBFObZVKRZZrLMlejjK65KCHKqIjsKZut0KPZdLriFSa7s65grtyT0mEqkNfjCQKvxxMDU8HydZbVZJbJNcKS6SKY1+MJIr/GQ5jX4yGMZvNrPMimgK04XM1rz+HgkdMxMPmiGx5ndjM7v3ukXd0Fk+bE1+qG50WbXFPcJDfJTT4zkztRGVih3ajxrNCr2JOv45zkJrlJbpKb3MJzPEyNZ/1HQRkWW/EoqLadR0Ht/VqgfYtEp2caZS2w+pRlRo9h+z3jlHxaq4BN62BVHUw7A5NdsGIVrC6BqZH0eMRGPVCjhSijs6zs1hkmaSzTJLC6BeaWgYwKYQ09A0azNSoGWLkE1orocKU1Hqbq8jM1nlRIjSfZRDbvcI0jWw9MaiY3rfGsafJVNDzcJDfJTXKT3ORTmHwNlYEVNZ6rkBrPVUiNJ4TxGg+v8fCGh5vkJrnJHTBJazyHtJ6zqPF4lwZSz/Fumhm2qPFQtqjxpBY1nnoebPnffZPIxtZ44hHXeBKVXDVQrkWiXN1lmaGxLDNl2TQDVlXBNAPszAZz6zRbCZHeYLLlrGhMVuVA1RaJqkqJZRmNZWWJZVIZTFbBtAyiuo2opNBsRUR2HZHhIorE5E8crrHwwxWFzZDDNbnqcE0+zeH6OhoebpKb5Ca5yV9vMv5cTD7huz+WxkIOoxwLWfm8Kx0LySzGQjZ+3nU9Jd5WCoEqJ4jEDsusVhgrMKxlgRXAKgumYs2VjggmLpgKRrNVoppl4hnWePhMotwkN8lNcpMvweTyTXNQYomve9NcC7tpruGm2esMPHrTTFj8F9w0J1S5EUhukejMKLIs4zJMnkosk6b4RkMEczNnhNUrYEUDzNDBbAWMZpOjecTFruUCnVokqtVdylqnhCkSyzJllpUzYLkC1icpiKo6IreOqIFsNV1GRLPVxCd67Cz5hI+drVeSjP4NhK+h4eEmuUlukpv89T2eVzWTaBoziR7ne+wMoXR+pCVWDZtJtLqYSRQzk4bMJLrXW8zGFDqTKPlGVDOJloqBSieIbItllRBWUBlWUgtFqANmVYD0FmU2mE1ZS6cM2ZZmEn3z96d3Hz9+fPfp3/9svCdfzAxpbz5++OL9+udWeLexyRfT8Lz596sgfPlwK+y0yf8RjztuMvD429+7bNL5cOt4vz982mGTt8F+/Ph1hw/X3z75Hr+++/oD5+SvHPBJhg749NYb8Hnzz3w/fvmRhqejKP4rYRSjfqUYQTitkMhjdWMeKpI+/wXmh4pWCpbyv1snYUnDd42OQr6rS+S7SsYiyZTKlHxBKRfIFihWBlsg2fju1dJ18vb2n/96P243PicPj6jam0btdVlIjnXZEd3SL79RbWqSi4uLi+sZafW74l68hv3z1Qu9KDnO/Ifzzcvh3m9pY55I5qB/7ZiD0XCy/G7Rm21tzpPIGQ2F+0G3ey/0r4Vu35f/LtybbW9XpHLGXWHW9x2edwWnO5ewOybN0flk/ipK870p3JjmeXdxvDoPn5P9z5f3s9n9nyvffUjW5AwGq5d6KnWvHWH02fQPWG/XjbxdutgYczwbPviSytn8DzBeb9OdwfVl/2c39cc1PneE7ueJtxnmZlfFu5n/c/DIK5C/1cU2TV443oF6Lkwu7u42OaC6F2PvmBXMlS9dhbZp0tfwYtX+MKlA+pemMx5vkGTbJkezVUtMRkQTuBxdDK7/CtmND+7ZLZvsz1a9ApeVc+/9YSaMI3NA/l5mf0KEdW/X5HDkrGxyhgMitLZd/whn95pj3iPodunVdq6tmhx6Lau5agP6EN6QP7gM3D48r8X32qbJ7t3Nzf2fG16oncHscjDfR935vBbO0pQP4Sa7w8tHrrlPre7Y14bpncF4HJj057UY98Mm7/hWw8F4sPLt189Wk7EwGi5dgXbtDnQu71AdL81r0X/fX7t7wMW1a/o/eOTO17fbj0EAAAAASUVORK5CYII=')
Out[71]:

Definicija: S $\pi(x)$ ćemo označavati broj prostih brojeva $p$ takvih da je $p \leqslant x$. Godine 1896. Hadamard i de la Valle Poussin su pokazali da je $\pi(x) \sim \frac{x}{ln x}$.

In [105]:
import matplotlib.pyplot as plt
from pylab import *
from numpy import *
x = linspace(2,999,1000)
y = x/log(x)
fig, axes = plt.subplots()
axes.plot(x,y,'r',label=r"$\pi(x)$")
axes.set_xlabel(r"$x$",fontsize=18)
axes.set_ylabel(r"$y$",fontsize=18)
axes.legend(loc=0)
axes.axhline(y=0,xmin=2,xmax=500)
axes.set_title('Distribucija prostih brojeva');