Аритметичке функције

У теорији бројева, аритметичка функција је генерално било која функција чији је домен скуп позитивних целих бројева, а кодомен је подскуп комплексних бројева. Харди и Рајт у своју дефиницију укључују захтев да аритметичка функција "изражава неко аритметичко својство броја n". Постоји и шира класа функција у теорији бројева које се не уклапају у ову дефиницију, на пример, функције за бројање простих бројева. Овај чланак пружа везе ка функцијама обе класе.

Пример аритметичке функције је делитељска функција, чија је вредност за позитиван цео број n једнака броју делитеља броја n.

Аритметичке функције су често изузетно неправилне (погледати табелу), али неке од њих имају развој у ред у терминима Рамануџановог збира.

Мултипликативне и адитивне функције

Аритметичка функција a је

• потпуно адитивна ако је a(mn) = a(m) + a(n) за све природне бројеве m и n;
• потпуно мултипликативна ако је a(1) = 1 и a(mn) = a(m)a(n) за све природне бројеве m и n;

Два цела броја m и n називају се узајамно прости ако је њихов највећи заједнички делилац 1, то јест, ако не постоји прост број који дели оба броја.

Тада је аритметичка функција a

• адитивна ако је a(mn) = a(m) + a(n) за све узајамно просте природне бројеве m и n;
• мултипликативна ако је a(1) = 1 и a(mn) = a(m)a(n) за све узајамно просте природне бројеве m и n.

Нотација

У овом чланку, ${\sum }_{p}f(p)$ и ${\prod }_{p}f(p)$ означавају да се сума или производ узимају преко свих простих бројева: $$\sum _{p}f(p)=f(2)+f(3)+f(5)+\cdots$$ и $$\prod _{p}f(p)=f(2)f(3)f(5)\cdots .$$ Слично, ${\sum }_{p^k}f(p^k)$ и ${\prod }_{p^k}f(p^k)$ означавају да се сума или производ узимају преко свих степена простих бројева са строго позитивним експонентом (дакле, Шаблон:Math није укључено): $$\sum _{p^k}f(p^k)=\sum _p\sum _{k>0}f(p^k)=f(2)+f(3)+f(4)+f(5)+f(7)+f(8)+f(9)+\cdots .$$

Нотације ${\sum }_{d\mid n}f(d)$ и ${\prod }_{d\mid n}f(d)$ означавају да се сума или производ узимају преко свих позитивних делитеља броја n, укључујући 1 и n. На пример, ако је Шаблон:Math, онда је $$\prod _{d\mid 12}f(d)=f(1)f(2)f(3)f(4)f(6)f(12).$$

Нотације се могу комбиновати: ${\sum }_{p\mid n}f(p)$ и ${\prod }_{p\mid n}f(p)$ означавају да се сума или производ узимају преко свих простих делитеља броја n. На пример, ако је n = 18, онда је $$\sum _{p\mid 18}f(p)=f(2)+f(3),$$ и слично, ${\sum }_{p^k\mid n}f(p^k)$ и ${\prod }_{p^k\mid n}f(p^k)$ означавају да се сума или производ узимају преко свих степена простих бројева који деле n. На пример, ако је n = 24, онда је $$\prod _{p^k\mid 24}f(p^k)=f(2)f(3)f(4)f(8).$$

Ω(n), ω(n), ν_p(n) – декомпозиција на просте степене

Основна теорема аритметике тврди да се сваки позитиван цео број n може јединствено представити као производ степена простих бројева: $n=p_1^{a_1}\cdots p_k^{a_k}$ где су p₁ < p₂ < ... < p_k прости бројеви, а a_j су позитивни цели бројеви. (1 је представљено празним производом.)

Често је згодно ово записати као бесконачан производ преко свих простих бројева, где сви осим коначног броја имају нулти експонент. Дефинише се p-адска валуација ν_p(n) као експонент највећег степена простог броја p који дели n. То јест, ако је p један од p_i, онда је ν_p(n) = a_i, иначе је нула. Тада је $$n=\prod _p{p}^{{\nu }_p(n)}.$$

У терминима наведеног, просте омега функције ω и Ω су дефинисане са Шаблон:Block indent Шаблон:Block indent

Да би се избегло понављање, формуле за функције наведене у овом чланку су, где год је то могуће, дате у терминима n и одговарајућих p_i, a_i, ω и Ω.

Мултипликативне функције

σ_k(n), τ(n), d(n) – функције делитеља

σ_k(n) је збир k-тих степена позитивних делитеља броја n, укључујући 1 и n, где је k комплексни број.

σ₁(n), збир (позитивних) делитеља броја n, обично се означава са σ(n).

Пошто је позитиван број на нулти степен једнак један, σ₀(n) је стога број (позитивних) делитеља броја n; обично се означава са d(n) или τ(n) (од немачког Teiler = делитељи). $${\sigma }_k(n)=\prod _{i=1}^{\omega (n)}\frac{p_i^{(a_i+1)k}-1}{p_i^k-1}=\prod _{i=1}^{\omega (n)}(1+p_i^k+p_i^{2k}+\cdots +p_i^{a_{i}k}).$$

Ако се у другом производу узме k = 0, добија се $$\tau (n)=d(n)=(1+a_1)(1+a_2)\cdots (1+a_{\omega (n)}).$$

φ(n) – Ојлерова фи функција

φ(n), Ојлерова фи функција, је број позитивних целих бројева који нису већи од n и који су узајамно прости са n. $$\phi (n)=n\prod _{p\mid n}(1-\frac{1}{p})=n\left(\frac{p_1-1}{p_1}\right)\left(\frac{p_2-1}{p_2}\right)\cdots \left(\frac{p_{\omega (n)}-1}{p_{\omega (n)}}\right).$$

J_k(n) – Жорданова фи функција

J_k(n), Жорданова фи функција, је број k-торки позитивних целих бројева мањих или једнаких n који заједно са n чине узајамно просту (k + 1)-торку. Она је генерализација Ојлерове фи функције, Шаблон:Math. $$J_k(n)=n^k\prod _{p\mid n}(1-\frac{1}{p^k})=n^k\left(\frac{p_1^k-1}{p_1^k}\right)\left(\frac{p_2^k-1}{p_2^k}\right)\cdots \left(\frac{p_{\omega (n)}^k-1}{p_{\omega (n)}^k}\right).$$

μ(n) – Мебијусова функција

μ(n), Мебијусова функција, важна је због формуле Мебијусове инверзије. Погледати Дирихлеова конволуција, испод. $$\mu (n)=\{\begin{array}{cc}(-1{)}^{\omega (n)}=(-1{)}^{\mathrm{\Omega }(n)}& \text{ако је }\omega (n)=\mathrm{\Omega }(n)\\ 0& \text{ако је }\omega (n)\ne \mathrm{\Omega }(n).\end{array}$$

Ово имплицира да је μ(1) = 1. (Јер је Ω(1) = ω(1) = 0.)

τ(n) – Рамануџанова тау функција

τ(n), Рамануџанова тау функција, дефинисана је својим идентитетом генераторне функције: $$\sum _{n\ge 1}\tau (n)q^n=q\prod _{n\ge 1}(1-q^n{)}^{24}.$$

Иако је тешко тачно рећи које "аритметичко својство n-а" она "изражава", (τ(n) је (2π)⁻¹² пута n-ти Фуријеов коефицијент у q-експанзији модуларне дискриминантне функције) укључена је међу аритметичке функције јер је мултипликативна и појављује се у идентитетима који укључују одређене σ_k(n) и r_k(n) функције (јер су и оне коефицијенти у развоју модуларних форми).

c_q(n) – Рамануџанов збир

c_q(n), Рамануџанов збир, је збир n-тих степена примитивних q-тих корена јединице: $$c_q(n)=\sum _{\stackrel{1\le a\le q}{gcd(a,q)=1}}{e}^{2\pi i\frac{a}{q}n}.$$

Иако је дефинисан као збир комплексних бројева (ирационалних за већину вредности q), он је цео број. За фиксну вредност n он је мултипликативан у q:

Ако су q и r узајамно прости, онда је $c_q(n)c_r(n)=c_{qr}(n).$

ψ(n) – Дедекиндова пси функција

Дедекиндова пси функција, коришћена у теорији модуларних функција, дефинисана је формулом $$\psi (n)=n\prod _{p|n}(1+\frac{1}{p}).$$

Потпуно мултипликативне функције

λ(n) – Лијувилова функција

λ(n), Лијувилова функција, дефинисана је са $$\lambda (n)=(-1{)}^{\mathrm{\Omega }(n)}.$$

χ(n) – карактери

Сви Дирихлеови карактери χ(n) су потпуно мултипликативни. Два карактера имају посебне ознаке:

Главни карактер (mod n) означава се са χ₀(a) (или χ₁(a)). Дефинисан је као $${\chi }_0(a)=\{\begin{array}{cc}1& \text{ако је }gcd(a,n)=1,\\ 0& \text{ако је }gcd(a,n)\ne 1.\end{array}$$

Квадратни карактер (mod n) означава се Јакобијевим симболом за непарно n (није дефинисан за парно n): $$\left(\frac{a}{n}\right)={\left(\frac{a}{p_1}\right)}^{a_1}{\left(\frac{a}{p_2}\right)}^{a_2}\cdots {\left(\frac{a}{p_{\omega (n)}}\right)}^{a_{\omega (n)}}.$$

У овој формули $(\frac{a}{p})$ је Лежандров симбол, дефинисан за све целе бројеве a и све непарне просте бројеве p са $$\left(\frac{a}{p}\right)=\{\begin{array}{cc}0& \text{ако је }a\equiv 0(\mathrm{mod}p),\\ +1& \text{ако је }a\equiv ̸0(\mathrm{mod}p)\text{ и за неки цео број }x,a\equiv x^2(\mathrm{mod}p)\\ -1& \text{ако такав }x\text{ не постоји}.\end{array}$$

Према уобичајеној конвенцији за празан производ, $\left(\frac{a}{1}\right)=1.$

Адитивне функције

ω(n) – различити прости делитељи

ω(n), дефинисана горе као број различитих простих бројева који деле n, је адитивна (погледати Просте омега функције).

Потпуно адитивне функције

Ω(n) – прости делитељи

Ω(n), дефинисана горе као број простих фактора броја n бројаних са вишеструкостима, је потпуно адитивна (погледати Просте омега функције).

ν_p(n) – p-адска валуација целог броја n

За фиксни прост број p, ν_p(n), дефинисана горе као експонент највећег степена броја p који дели n, је потпуно адитивна.

Логаритамски извод

$\mathrm{ld}(n)=\frac{D(n)}{n}=\sum _{\stackrel{p\mid n}{p\text{ прост}}}\frac{v_p(n)}{p}$, где је $D(n)$ аритметички извод.

Ни мултипликативне ни адитивне

π(x), Π(x), ϑ(x), ψ(x) – функције расподеле простих бројева

Ове важне функције (које нису аритметичке функције) дефинисане су за ненегативне реалне аргументе и користе се у различитим исказима и доказима теореме о простим бројевима. Оне су суматорне функције (погледати главни одељак испод) аритметичких функција које нису ни мултипликативне ни адитивне.

π(x), функција расподеле простих бројева, је број простих бројева који нису већи од x. Она је суматорна функција карактеристичне функције простих бројева. $$\pi (x)=\sum _{p\le x}1$$

Сродна функција броји степене простих бројева са тежином 1 за просте бројеве, 1/2 за њихове квадрате, 1/3 за кубове, итд. Она је суматорна функција аритметичке функције која узима вредност 1/k за целе бројеве који су k-ти степен неког простог броја, а вредност 0 за друге целе бројеве. $$\mathrm{\Pi }(x)=\sum _{p^k\le x}\frac{1}{k}.$$

ϑ(x) и ψ(x), Чебишевљеве функције, дефинисане су као збирови природних логаритама простих бројева који нису већи од x. $$\vartheta (x)=\sum _{p\le x}\log p,$$ $$\psi (x)=\sum _{p^k\le x}\log p.$$

Друга Чебишевљева функција ψ(x) је суматорна функција фон Манголтове функције која је описана испод.

Λ(n) – фон Манголтова функција

Λ(n), фон Манголтова функција, је 0 осим ако је аргумент n степен простог броја Шаблон:Math, у ком случају је то природни логаритам простог броја p: $$\mathrm{\Lambda }(n)=\{\begin{array}{cc}\log p& \text{ако је }n=2,3,4,5,7,8,9,11,13,16,\dots =p^k\text{ степен простог броја}\\ 0& \text{ако }n=1,6,10,12,14,15,18,20,21,\dots \text{ није степен простог броја}.\end{array}$$

p(n) – партициона функција

p(n), партициона функција, је број начина представљања n као збира позитивних целих бројева, где се две репрезентације са истим сабирцима у различитом редоследу не рачунају као различите: $$p(n)=\left|\{(a_1,a_2,\dots a_k):0<a_1\le a_2\le \cdots \le a_k\wedge n=a_1+a_2+\cdots +a_k\}\right|.$$

λ(n) – Кармајклова функција

λ(n), Кармајклова функција, је најмањи позитиван број такав да је $a^{\lambda (n)}\equiv 1(\mathrm{mod}n)$ за све a узајамно просте са n. Еквивалентно, то је најмањи заједнички садржалац редова елемената мултипликативне групе целих бројева по модулу n.

За степене непарних простих бројева и за 2 и 4, λ(n) је једнака Ојлеровој фи функцији од n; за степене броја 2 веће од 4, једнака је половини Ојлерове фи функције од n: $$\lambda (n)=\{\begin{array}{cc}\varphi (n)& \text{ако је }n=2,3,4,5,7,9,11,13,17,19,23,25,27,\dots \\ \frac{1}{2}\varphi (n)& \text{ако је }n=8,16,32,64,\dots \end{array}$$ а за опште n то је најмањи заједнички садржалац од λ за сваки од фактора степена простог броја од n: $$\lambda (p_1^{a_1}{p}_2^{a_2}\dots p_{\omega (n)}^{a_{\omega (n)}})=\mathrm{lcm}[\lambda (p_1^{a_1}),\lambda (p_2^{a_2}),\dots ,\lambda (p_{\omega (n)}^{a_{\omega (n)}})].$$

h(n) – број класе

h(n), функција броја класе, је ред групе класа идеала алгебарског проширења рационалних бројева са дискриминантом n. Нотација је двосмислена, јер генерално постоји много проширења са истом дискриминантом. Погледати квадратно поље и циклотомично поље за класичне примере.

r_k(n) – збир k квадрата

r_k(n) је број начина на које се n може представити као збир k квадрата, где се репрезентације које се разликују само у редоследу сабирака или у знацима квадратних корена рачунају као различите. $$r_k(n)=\left|\{(a_1,a_2,\dots ,a_k):n=a_1^2+a_2^2+\cdots +a_k^2\}\right|$$

D(n) – Аритметички извод

Користећи Хевисајдову нотацију за извод, аритметички извод D(n) је функција таква да

• $D(n)=1$ ако је n прост, и
• $D(mn)=mD(n)+D(m)n$ (правило производа)

Суматорне функције

За дату аритметичку функцију a(n), њена суматорна функција A(x) је дефинисана са $$A(x):=\sum _{n\le x}a(n).$$ A се може сматрати функцијом реалне променљиве. За дати позитиван цео број m, A је константна дуж отворених интервала m < x < m + 1, и има скоковити дисконтинуитет у сваком целом броју за који је a(m) ≠ 0.

Пошто се такве функције често представљају редовима и интегралима, да би се постигла тачкаста конвергенција, уобичајено је дефинисати вредност у дисконтинуитетима као просек вредности са леве и десне стране: $$A_0(m):=\frac{1}{2}(\sum _{n<m}a(n)+\sum _{n\le m}a(n))=A(m)-\frac{1}{2}a(m).$$

Појединачне вредности аритметичких функција могу дивље флуктуирати – као у већини горе наведених примера. Суматорне функције "изглађују" ове флуктуације. У неким случајевима је могуће пронаћи асимптотско понашање за суматорну функцију за велико x. Класичан пример овог феномена дат је суматорном функцијом делитеља, суматорном функцијом од d(n), броја делитеља од n: $$\underset{n\to \mathrm{\infty }}{lim\; inf}d(n)=2$$ $$\underset{n\to \mathrm{\infty }}{lim\; sup}\frac{\log d(n)\log \log n}{\log n}=\log 2$$ $$\underset{n\to \mathrm{\infty }}{lim}\frac{d(1)+d(2)+\cdots +d(n)}{\log (1)+\log (2)+\cdots +\log (n)}=1.$$

Просечан ред аритметичке функције је нека једноставнија или боље схваћена функција која има исту суматорну функцију асимптотски, и стога узима исте вредности "у просеку". Кажемо да је g просечан ред од f ако је $$\sum _{n\le x}f(n)\sim \sum _{n\le x}g(n)$$

када x тежи бесконачности. Пример изнад показује да d(n) има просечан ред log(n).

Дирихлеова конволуција

За дату аритметичку функцију a(n), нека је F_a(s), за комплексно s, функција дефинисана одговарајућим Дирихлеовим редом (где конвергира): $$F_a(s):=\sum _{n=1}^{\mathrm{\infty }}\frac{a(n)}{n^s}.$$ F_a(s) се назива генераторна функција од a(n). Најједноставнији такав ред, који одговара константној функцији a(n) = 1 за свако n, је ζ(s), Риманова зета-функција.

Генераторна функција Мебијусове функције је инверзна функција зета-функције: $$\zeta (s)\sum _{n=1}^{\mathrm{\infty }}\frac{\mu (n)}{n^s}=1,\mathrm{\Re }s>1.$$

Размотримо две аритметичке функције a и b и њихове одговарајуће генераторне функције F_a(s) и F_b(s). Производ F_a(s)F_b(s) може се израчунати на следећи начин: $$F_a(s)F_b(s)=\left(\sum _{m=1}^{\mathrm{\infty }}\frac{a(m)}{m^s}\right)\left(\sum _{n=1}^{\mathrm{\infty }}\frac{b(n)}{n^s}\right).$$

Једноставна вежба је показати да ако је c(n) дефинисано са $$c(n):=\sum _{ij=n}a(i)b(j)=\sum _{i\mid n}a(i)b\left(\frac{n}{i}\right),$$ онда је $$F_c(s)=F_a(s)F_b(s).$$

Ова функција c се назива Дирихлеова конволуција од a и b, и означава се са $a\ast b$.

Посебно важан случај је конволуција са константном функцијом a(n) = 1 за свако n, што одговара множењу генераторне функције са зета-функцијом: $$g(n)=\sum _{d\mid n}f(d).$$

Множењем инверзом зета-функције добија се Мебијусова формула инверзије: $$f(n)=\sum _{d\mid n}\mu \left(\frac{n}{d}\right)g(d).$$

Ако је f мултипликативна, онда је и g. Ако је f потпуно мултипликативна, онда је g мултипликативна, али може, а и не мора бити потпуно мултипликативна.

Релације међу функцијама

Постоји велики број формула које повезују аритметичке функције међусобно и са функцијама анализе, посебно степенима, коренима, те експоненцијалном и логаритамском функцијом. Страница идентитети збира делитеља садржи много више генерализованих и сродних примера идентитета који укључују аритметичке функције.

Ево неколико примера:

Дирихлеове конволуције

$\sum _{\delta \mid n}\mu (\delta )=\sum _{\delta \mid n}\lambda \left(\frac{n}{\delta }\right)|\mu (\delta )|=\{\begin{array}{cc}1& \text{ако је }n=1\\ 0& \text{ако је }n\ne 1\end{array}$     где је λ Лијувилова функција.

$\sum _{\delta \mid n}\phi (\delta )=n.$      

$\phi (n)=\sum _{\delta \mid n}\mu \left(\frac{n}{\delta }\right)\delta =n\sum _{\delta \mid n}\frac{\mu (\delta )}{\delta }.$       Мебијусова инверзија

$\sum _{d\mid n}{J}_k(d)=n^k.$      

$J_k(n)=\sum _{\delta \mid n}\mu \left(\frac{n}{\delta }\right){\delta }^k=n^k\sum _{\delta \mid n}\frac{\mu (\delta )}{{\delta }^k}.$       Мебијусова инверзија

$\sum _{\delta \mid n}{\delta }^s{J}_r(\delta )J_s\left(\frac{n}{\delta }\right)=J_{r+s}(n)$      

$\sum _{\delta \mid n}\phi (\delta )d\left(\frac{n}{\delta }\right)=\sigma (n).$      

$\sum _{\delta \mid n}|\mu (\delta )|=2^{\omega (n)}.$      

$|\mu (n)|=\sum _{\delta \mid n}\mu \left(\frac{n}{\delta }\right)2^{\omega (\delta )}.$       Мебијусова инверзија

$\sum _{\delta \mid n}{2}^{\omega (\delta )}=d(n^2).$      

$2^{\omega (n)}=\sum _{\delta \mid n}\mu \left(\frac{n}{\delta }\right)d({\delta }^2).$       Мебијусова инверзија

$\sum _{\delta \mid n}d({\delta }^2)=d^2(n).$      

$d(n^2)=\sum _{\delta \mid n}\mu \left(\frac{n}{\delta }\right)d^2(\delta ).$       Мебијусова инверзија

$\sum _{\delta \mid n}d\left(\frac{n}{\delta }\right)2^{\omega (\delta )}=d^2(n).$      

$\sum _{\delta \mid n}\lambda (\delta )=\{\begin{array}{cc}& 1\text{ ако је }n\text{ квадрат }\\ & 0\text{ ако }n\text{ није квадрат.}\end{array}$     где је λ Лијувилова функција.

$\sum _{\delta \mid n}\mathrm{\Lambda }(\delta )=\log n.$      

$\mathrm{\Lambda }(n)=\sum _{\delta \mid n}\mu \left(\frac{n}{\delta }\right)\log (\delta ).$       Мебијусова инверзија

Збирови квадрата

За све $k\ge 4,r_k(n)>0.$     (Лагранжова теорема о четири квадрата).

$r_2(n)=4\sum _{d\mid n}\left(\frac{-4}{d}\right),$

где Кронекеров симбол има вредности

$\left(\frac{-4}{n}\right)=\{\begin{array}{cc}+1& \text{ако је }n\equiv 1(\mathrm{mod}4)\\ -1& \text{ако је }n\equiv 3(\mathrm{mod}4)\\ 0& \text{ако је }n\text{ паран}.\end{array}$

Постоји формула за r₃ у одељку о бројевима класе испод. $$r_4(n)=8\sum _{\stackrel{d\mid n}{4\nmid d}}d=8(2+(-1{)}^n)\sum _{\stackrel{d\mid n}{2\nmid d}}d=\{\begin{array}{cc}8\sigma (n)& \text{ако је }n\text{ непаран }\\ 24\sigma \left(\frac{n}{2^{\nu }}\right)& \text{ако је }n\text{ паран }\end{array},$$ где је Шаблон:Math.     $$r_6(n)=16\sum _{d\mid n}\chi \left(\frac{n}{d}\right)d^2-4\sum _{d\mid n}\chi (d)d^2,$$ где је $\chi (n)=\left(\frac{-4}{n}\right).$

Дефинишимо функцију Шаблон:Math као $${\sigma }_k^{\ast }(n)=(-1{)}^n\sum _{d\mid n}(-1{)}^d{d}^k=\{\begin{array}{cc}\sum _{d\mid n}{d}^k={\sigma }_k(n)& \text{ако је }n\text{ непаран }\\ \sum _{\stackrel{d\mid n}{2\mid d}}{d}^k-\sum _{\stackrel{d\mid n}{2\nmid d}}{d}^k& \text{ако је }n\text{ паран}.\end{array}$$

То јест, ако је n непаран, Шаблон:Math је збир k-тих степена делитеља броја n, то јест, Шаблон:Math а ако је n паран, то је збир k-тих степена парних делитеља броја n минус збир k-тих степена непарних делитеља броја n.

$r_8(n)=16{\sigma }_3^{\ast }(n).$    

Усвојимо конвенцију да је Рамануџанов Шаблон:Math ако x није цео број.

$r_{24}(n)=\frac{16}{691}{\sigma }_{11}^{\ast }(n)+\frac{128}{691}\{(-1{)}^{n-1}259\tau (n)-512\tau \left(\frac{n}{2}\right)\}$    

Конволуције збирова делитеља

Овде "конволуција" не значи "Дирихлеова конволуција", већ се односи на формулу за коефицијенте производа два степена реда:

$\left(\sum _{n=0}^{\mathrm{\infty }}{a}_n{x}^n\right)\left(\sum _{n=0}^{\mathrm{\infty }}{b}_n{x}^n\right)=\sum _{i=0}^{\mathrm{\infty }}\sum _{j=0}^{\mathrm{\infty }}{a}_i{b}_j{x}^{i+j}=\sum _{n=0}^{\mathrm{\infty }}\left(\sum _{i=0}^n{a}_i{b}_{n-i}\right)x^n=\sum _{n=0}^{\mathrm{\infty }}{c}_n{x}^n.$

Низ $c_n=\sum _{i=0}^n{a}_i{b}_{n-i}$ назива се конволуција или Кошијев производ низова a_n и b_n. Шаблон:BrОве формуле се могу доказати аналитички (погледати Ајзенштајнов ред) или елементарним методама.

${\sigma }_3(n)=\frac{1}{5}\{6n{\sigma }_1(n)-{\sigma }_1(n)+12\sum _{0<k<n}{\sigma }_1(k){\sigma }_1(n-k)\}.$    

${\sigma }_5(n)=\frac{1}{21}\{10(3n-1){\sigma }_3(n)+{\sigma }_1(n)+240\sum _{0<k<n}{\sigma }_1(k){\sigma }_3(n-k)\}.$    

$\begin{array}{cc}{\sigma }_7(n)& =\frac{1}{20}\{21(2n-1){\sigma }_5(n)-{\sigma }_1(n)+504\sum _{0<k<n}{\sigma }_1(k){\sigma }_5(n-k)\}\\ & ={\sigma }_3(n)+120\sum _{0<k<n}{\sigma }_3(k){\sigma }_3(n-k).\end{array}$    

$\begin{array}{cc}{\sigma }_9(n)& =\frac{1}{11}\{10(3n-2){\sigma }_7(n)+{\sigma }_1(n)+480\sum _{0<k<n}{\sigma }_1(k){\sigma }_7(n-k)\}\\ & =\frac{1}{11}\{21{\sigma }_5(n)-10{\sigma }_3(n)+5040\sum _{0<k<n}{\sigma }_3(k){\sigma }_5(n-k)\}.\end{array}$    

$\tau (n)=\frac{65}{756}{\sigma }_{11}(n)+\frac{691}{756}{\sigma }_5(n)-\frac{691}{3}\sum _{0<k<n}{\sigma }_5(k){\sigma }_5(n-k),$     где је τ(n) Рамануџанова функција.    

Пошто су σ_k(n) (за природни број k) и τ(n) цели бројеви, горенаведене формуле се могу користити за доказивање конгруенција за функције. Погледати Рамануџанова тау функција за неке примере.

Проширимо домен партиционе функције постављањем Шаблон:Math

$p(n)=\frac{1}{n}\sum _{1\le k\le n}\sigma (k)p(n-k).$       Ова рекуренција се може користити за израчунавање p(n).

Повезано са бројем класе

Петер Густав Лежен Дирихле је открио формуле које повезују број класе h квадратних бројних поља са Јакобијевим симболом.

Цео број D се назива фундаментални дискриминант ако је то дискриминанта квадратног бројног поља. Ово је еквивалентно са D ≠ 1 и или а) D је безквадратан и D ≡ 1 (mod 4) или б) D ≡ 0 (mod 4), D/4 је безквадратан, и D/4 ≡ 2 или 3 (mod 4).

Проширимо Јакобијев симбол да прихвата парне бројеве у "имениоцу" дефинисањем Кронекеровог симбола: $$\left(\frac{a}{2}\right)=\{\begin{array}{cc}0& \text{ако је }a\text{ паран}\\ (-1{)}^{\frac{a^2-1}{8}}& \text{ ако је }a\text{ непаран. }\end{array}$$

Тада ако је D < −4 фундаментални дискриминант $$\begin{array}{cc}h(D)& =\frac{1}{D}\sum _{r=1}^{|D|}r\left(\frac{D}{r}\right)\\ & =\frac{1}{2-\left(\frac{D}{2}\right)}\sum _{r=1}^{|D|/2}\left(\frac{D}{r}\right).\end{array}$$

Такође постоји формула која повезује r₃ и h. Опет, нека је D фундаментални дискриминант, D < −4. Тада $$r_3(|D|)=12(1-\left(\frac{D}{2}\right))h(D).$$

Повезано са расподелом простих бројева

Нека је $H_n=1+\frac{1}{2}+\frac{1}{3}+\cdots +\frac{1}{n}$   n-ти хармонијски број. Тада

$\sigma (n)\le H_n+e^{H_n}\log H_n$   важи за сваки природни број n ако и само ако је Риманова хипотеза тачна.    

Риманова хипотеза је такође еквивалентна тврдњи да, за све n > 5040, $$\sigma (n)<e^{\gamma }n\log \log n$$ (где је γ Ојлер-Маскеронијева константа). Ово је Робинова теорема.

$\sum _p{\nu }_p(n)=\mathrm{\Omega }(n).$

$\psi (x)=\sum _{n\le x}\mathrm{\Lambda }(n).$    

$\mathrm{\Pi }(x)=\sum _{n\le x}\frac{\mathrm{\Lambda }(n)}{\log n}.$    

$e^{\theta (x)}=\prod _{p\le x}p.$    

$e^{\psi (x)}=\mathrm{lcm}[1,2,\dots ,\lfloor x\rfloor ].$    

Менонов идентитет

Године 1965. П. Кесава Менон је доказао $$\sum _{\stackrel{1\le k\le n}{gcd(k,n)=1}}gcd(k-1,n)=\phi (n)d(n).$$

Ово су генерализовали бројни математичари. На пример,

• Б. Сури $$\sum _{\stackrel{1\le k_1,k_2,\dots ,k_s\le n}{gcd(k_1,n)=1}}gcd(k_1-1,k_2,\dots ,k_s,n)=\phi (n){\sigma }_{s-1}(n).$$
• Н. Рао $$\sum _{\stackrel{1\le k_1,k_2,\dots ,k_s\le n}{gcd(k_1,k_2,\dots ,k_s,n)=1}}gcd(k_1-a_1,k_2-a_2,\dots ,k_s-a_s,n{)}^s=J_s(n)d(n),$$ где су a₁, a₂, ..., a_s цели бројеви, gcd(a₁, a₂, ..., a_s, n) = 1.
• Ласло Фејеш Тот $$\sum _{\stackrel{1\le k\le m}{gcd(k,m)=1}}gcd(k^2-1,m_1)gcd(k^2-1,m_2)=\phi (n)\sum _{\stackrel{d_1\mid m_1}{d_2\mid m_2}}\phi (gcd(d_1,d_2))2^{\omega (\mathrm{lcm}(d_1,d_2))},$$ где су m₁ и m₂ непарни, m = lcm(m₁, m₂).

У ствари, ако је f било која аритметичка функција $$\sum _{\stackrel{1\le k\le n}{gcd(k,n)=1}}f(gcd(k-1,n))=\phi (n)\sum _{d\mid n}\frac{(\mu \ast f)(d)}{\phi (d)},$$ где $\ast$ представља Дирихлеову конволуцију.

Разно

Нека су m и n различити, непарни и позитивни. Тада Јакобијев симбол задовољава закон квадратног реципроцитета: $$\left(\frac{m}{n}\right)\left(\frac{n}{m}\right)=(-1{)}^{(m-1)(n-1)/4}.$$

Нека је D(n) аритметички извод. Тада је логаритамски извод $$\frac{D(n)}{n}=\sum _{\stackrel{p\mid n}{p\text{ прост}}}\frac{v_p(n)}{p}.$$ Погледати Аритметички извод за детаље.

Нека је λ(n) Лијувилова функција. Тада

$|\lambda (n)|\mu (n)=\lambda (n)|\mu (n)|=\mu (n),$     и

$\lambda (n)\mu (n)=|\mu (n)|={\mu }^2(n).$    

Нека је λ(n) Кармајклова функција. Тада

$\lambda (n)\mid \varphi (n).$     Даље,

$\lambda (n)=\varphi (n)\text{ ако и само ако }n=\{\begin{array}{c}1,2,4;\\ 3,5,7,9,11,\dots \text{ (то јест, }{p}^k\text{, где је }p\text{ непаран прост број)};\\ 6,10,14,18,\dots \text{ (то јест, }2p^k\text{, где је }p\text{ непаран прост број)}.\end{array}$

Погледати Мултипликативна група целих бројева по модулу n и Примитивни корен по модулу n.  

$2^{\omega (n)}\le d(n)\le 2^{\mathrm{\Omega }(n)}.$    

$\frac{6}{{\pi }^2}<\frac{\varphi (n)\sigma (n)}{n^2}<1.$    

$\begin{array}{cc}{c}_q(n)& =\frac{\mu \left(\frac{q}{gcd(q,n)}\right)}{\varphi \left(\frac{q}{gcd(q,n)}\right)}\varphi (q)\\ & =\sum _{\delta \mid gcd(q,n)}\mu \left(\frac{q}{\delta }\right)\delta .\end{array}$         Приметити да је  $\varphi (q)=\sum _{\delta \mid q}\mu \left(\frac{q}{\delta }\right)\delta .$    

$c_q(1)=\mu (q).$

$c_q(q)=\varphi (q).$

$\sum _{\delta \mid n}{d}^3(\delta )={(\sum _{\delta \mid n}d(\delta ))}^2.$       Упоредити ово са Шаблон:Math

$d(uv)=\sum _{\delta \mid gcd(u,v)}\mu (\delta )d\left(\frac{u}{\delta }\right)d\left(\frac{v}{\delta }\right).$    

${\sigma }_k(u){\sigma }_k(v)=\sum _{\delta \mid gcd(u,v)}{\delta }^k{\sigma }_k\left(\frac{uv}{{\delta }^2}\right).$    

$\tau (u)\tau (v)=\sum _{\delta \mid gcd(u,v)}{\delta }^{11}\tau \left(\frac{uv}{{\delta }^2}\right),$     где је τ(n) Рамануџанова функција.    

Првих 100 вредности неких аритметичких функција

n	факторизација	φ(n)	ω(n)	Ω(n)	λ(n)	μ(n)	Λ(n)	π(n)	σ0(n)	σ1(n)	σ2(n)	r2(n)	r3(n)	r4(n)
1	1	1	0	0	1	1	0	0	1	1	1	4	6	8
2	2	1	1	1	−1	−1	0.69	1	2	3	5	4	12	24
3	3	2	1	1	−1	−1	1.10	2	2	4	10	0	8	32
4	22	2	1	2	1	0	0.69	2	3	7	21	4	6	24
5	5	4	1	1	−1	−1	1.61	3	2	6	26	8	24	48
6	2 · 3	2	2	2	1	1	0	3	4	12	50	0	24	96
7	7	6	1	1	−1	−1	1.95	4	2	8	50	0	0	64
8	23	4	1	3	−1	0	0.69	4	4	15	85	4	12	24
9	32	6	1	2	1	0	1.10	4	3	13	91	4	30	104
10	2 · 5	4	2	2	1	1	0	4	4	18	130	8	24	144
11	11	10	1	1	−1	−1	2.40	5	2	12	122	0	24	96
12	22 · 3	4	2	3	−1	0	0	5	6	28	210	0	8	96
13	13	12	1	1	−1	−1	2.56	6	2	14	170	8	24	112
14	2 · 7	6	2	2	1	1	0	6	4	24	250	0	48	192
15	3 · 5	8	2	2	1	1	0	6	4	24	260	0	0	192
16	24	8	1	4	1	0	0.69	6	5	31	341	4	6	24
17	17	16	1	1	−1	−1	2.83	7	2	18	290	8	48	144
18	2 · 32	6	2	3	−1	0	0	7	6	39	455	4	36	312
19	19	18	1	1	−1	−1	2.94	8	2	20	362	0	24	160
20	22 · 5	8	2	3	−1	0	0	8	6	42	546	8	24	144
21	3 · 7	12	2	2	1	1	0	8	4	32	500	0	48	256
22	2 · 11	10	2	2	1	1	0	8	4	36	610	0	24	288
23	23	22	1	1	−1	−1	3.14	9	2	24	530	0	0	192
24	23 · 3	8	2	4	1	0	0	9	8	60	850	0	24	96
25	52	20	1	2	1	0	1.61	9	3	31	651	12	30	248
26	2 · 13	12	2	2	1	1	0	9	4	42	850	8	72	336
27	33	18	1	3	−1	0	1.10	9	4	40	820	0	32	320
28	22 · 7	12	2	3	−1	0	0	9	6	56	1050	0	0	192
29	29	28	1	1	−1	−1	3.37	10	2	30	842	8	72	240
30	2 · 3 · 5	8	3	3	−1	−1	0	10	8	72	1300	0	48	576
31	31	30	1	1	−1	−1	3.43	11	2	32	962	0	0	256
32	25	16	1	5	−1	0	0.69	11	6	63	1365	4	12	24
33	3 · 11	20	2	2	1	1	0	11	4	48	1220	0	48	384
34	2 · 17	16	2	2	1	1	0	11	4	54	1450	8	48	432
35	5 · 7	24	2	2	1	1	0	11	4	48	1300	0	48	384
36	22 · 32	12	2	4	1	0	0	11	9	91	1911	4	30	312
37	37	36	1	1	−1	−1	3.61	12	2	38	1370	8	24	304
38	2 · 19	18	2	2	1	1	0	12	4	60	1810	0	72	480
39	3 · 13	24	2	2	1	1	0	12	4	56	1700	0	0	448
40	23 · 5	16	2	4	1	0	0	12	8	90	2210	8	24	144
41	41	40	1	1	−1	−1	3.71	13	2	42	1682	8	96	336
42	2 · 3 · 7	12	3	3	−1	−1	0	13	8	96	2500	0	48	768
43	43	42	1	1	−1	−1	3.76	14	2	44	1850	0	24	352
44	22 · 11	20	2	3	−1	0	0	14	6	84	2562	0	24	288
45	32 · 5	24	2	3	−1	0	0	14	6	78	2366	8	72	624
46	2 · 23	22	2	2	1	1	0	14	4	72	2650	0	48	576
47	47	46	1	1	−1	−1	3.85	15	2	48	2210	0	0	384
48	24 · 3	16	2	5	−1	0	0	15	10	124	3410	0	8	96
49	72	42	1	2	1	0	1.95	15	3	57	2451	4	54	456
50	2 · 52	20	2	3	−1	0	0	15	6	93	3255	12	84	744
51	3 · 17	32	2	2	1	1	0	15	4	72	2900	0	48	576
52	22 · 13	24	2	3	−1	0	0	15	6	98	3570	8	24	336
53	53	52	1	1	−1	−1	3.97	16	2	54	2810	8	72	432
54	2 · 33	18	2	4	1	0	0	16	8	120	4100	0	96	960
55	5 · 11	40	2	2	1	1	0	16	4	72	3172	0	0	576
56	23 · 7	24	2	4	1	0	0	16	8	120	4250	0	48	192
57	3 · 19	36	2	2	1	1	0	16	4	80	3620	0	48	640
58	2 · 29	28	2	2	1	1	0	16	4	90	4210	8	24	720
59	59	58	1	1	−1	−1	4.08	17	2	60	3482	0	72	480
60	22 · 3 · 5	16	3	4	1	0	0	17	12	168	5460	0	0	576
61	61	60	1	1	−1	−1	4.11	18	2	62	3722	8	72	496
62	2 · 31	30	2	2	1	1	0	18	4	96	4810	0	96	768
63	32 · 7	36	2	3	−1	0	0	18	6	104	4550	0	0	832
64	26	32	1	6	1	0	0.69	18	7	127	5461	4	6	24
65	5 · 13	48	2	2	1	1	0	18	4	84	4420	16	96	672
66	2 · 3 · 11	20	3	3	−1	−1	0	18	8	144	6100	0	96	1152
67	67	66	1	1	−1	−1	4.20	19	2	68	4490	0	24	544
68	22 · 17	32	2	3	−1	0	0	19	6	126	6090	8	48	432
69	3 · 23	44	2	2	1	1	0	19	4	96	5300	0	96	768
70	2 · 5 · 7	24	3	3	−1	−1	0	19	8	144	6500	0	48	1152
71	71	70	1	1	−1	−1	4.26	20	2	72	5042	0	0	576
72	23 · 32	24	2	5	−1	0	0	20	12	195	7735	4	36	312
73	73	72	1	1	−1	−1	4.29	21	2	74	5330	8	48	592
74	2 · 37	36	2	2	1	1	0	21	4	114	6850	8	120	912
75	3 · 52	40	2	3	−1	0	0	21	6	124	6510	0	56	992
76	22 · 19	36	2	3	−1	0	0	21	6	140	7602	0	24	480
77	7 · 11	60	2	2	1	1	0	21	4	96	6100	0	96	768
78	2 · 3 · 13	24	3	3	−1	−1	0	21	8	168	8500	0	48	1344
79	79	78	1	1	−1	−1	4.37	22	2	80	6242	0	0	640
80	24 · 5	32	2	5	−1	0	0	22	10	186	8866	8	24	144
81	34	54	1	4	1	0	1.10	22	5	121	7381	4	102	968
82	2 · 41	40	2	2	1	1	0	22	4	126	8410	8	48	1008
83	83	82	1	1	−1	−1	4.42	23	2	84	6890	0	72	672
84	22 · 3 · 7	24	3	4	1	0	0	23	12	224	10500	0	48	768
85	5 · 17	64	2	2	1	1	0	23	4	108	7540	16	48	864
86	2 · 43	42	2	2	1	1	0	23	4	132	9250	0	120	1056
87	3 · 29	56	2	2	1	1	0	23	4	120	8420	0	0	960
88	23 · 11	40	2	4	1	0	0	23	8	180	10370	0	24	288
89	89	88	1	1	−1	−1	4.49	24	2	90	7922	8	144	720
90	2 · 32 · 5	24	3	4	1	0	0	24	12	234	11830	8	120	1872
91	7 · 13	72	2	2	1	1	0	24	4	112	8500	0	48	896
92	22 · 23	44	2	3	−1	0	0	24	6	168	11130	0	0	576
93	3 · 31	60	2	2	1	1	0	24	4	128	9620	0	48	1024
94	2 · 47	46	2	2	1	1	0	24	4	144	11050	0	96	1152
95	5 · 19	72	2	2	1	1	0	24	4	120	9412	0	0	960
96	25 · 3	32	2	6	1	0	0	24	12	252	13650	0	24	96
97	97	96	1	1	−1	−1	4.57	25	2	98	9410	8	48	784
98	2 · 72	42	2	3	−1	0	0	25	6	171	12255	4	108	1368
99	32 · 11	60	2	3	−1	0	0	25	6	156	11102	0	72	1248
100	22 · 52	40	2	4	1	0	0	25	9	217	13671	12	30	744
n	факторизација	φ(n)	ω(n)	Ω(n)	λ(n)	μ(n)	Λ(n)	π(n)	σ0(n)	σ1(n)	σ2(n)	r2(n)	r3(n)	r4(n)

Референце

• Шаблон:Citation
• Шаблон:Citation
• Шаблон:Citation
• Шаблон:Citation
• Шаблон:Cite book
• Шаблон:Citation
• Шаблон:Hardy and Wright
• Шаблон:Citation
• Шаблон:Citation
• Шаблон:Citation
• Шаблон:Citation
• Шаблон:Citation
• Шаблон:Citation
• Шаблон:Citation
• Шаблон:Citation
• Шаблон:Citation
• Шаблон:Citation
• Шаблон:Citation

Литература

• Шаблон:Citation

Спољашње везе

• Шаблон:Springer
• Matthew Holden, Michael Orrison, Michael Varble Још једна генерализација Ојлерове фи функције
• Huard, Ou, Spearman, and Williams. Елементарна евалуација одређених конволуционих сума које укључују функције делитеља
• Dineva, Rosica, Ојлерова фи, Мебијусова и функције делитеља Шаблон:Webarchive
• László Tóth, Менонов идентитет и аритметички збирови који представљају функције више променљивих