Прости числа - Задачи и Решения

[Titu_Andrescu]

1. Да се докаже, че ако [tex]p[/tex] е просто число, което не дели цялото число [tex]a[/tex], то [tex]a^{p-1}-1[/tex] се дели на [tex]p[/tex].
(малка Теорема на Пиер дьо Ферма)

[Реклама]

[Titu_Andrescu]

1. Решение.

Лема . За всяко просто число [tex]p[/tex] и [tex]x,y\in \mathbb{Z}[/tex], [tex](x\pm y)^p\equiv x^p\pm y^p (mod p)[/tex].
Д-во. От биномната теорема имаме, че [tex](x\pm y)^n=\sum_{i=1}^{n}{n\choose i}x^iy^{n-i}[/tex], където [tex]{n\choose i}=\frac{n!}{i!(n-1)!}[/tex]. Тъй като всички биномни коефициенти са цели числа и за [tex]0<i<p[/tex] нито един от знаменателите им не съдържа [tex]p[/tex], то тогава числителите на коефициентите трябва да се делят на [tex]p[/tex], т.е. [tex]{p\choose i}\equiv 0 (mod p), 0<i<p[/tex], с което лемата е доказана.

Сега, за да докажем теоремата ще използваме индукция относно [tex]a[/tex]. Нека [tex]k^p\equiv k (mod p)[/tex], за някое [tex]k\in \mathbb{Z}[/tex]. Да разгледаме [tex](k\pm 1)^p[/tex]. От лемата следва, че [tex](k\pm 1)^p\equiv k^p\pm 1^p\equiv k\pm 1 (mod p)[/tex], което е исканото твърдение за [tex]a=k+1[/tex].

[Titu_Andrescu]

2. Да се намерят всички прости числа [tex](p,q,r)[/tex], за които е изпълнено
[tex]p|q^r+1, q|r^p+1, r|p^q+1[/tex].
(Рейд Бъртон)

[Мирослав Стоенчев]

Р-е: Да допуснем, че [tex]p,q,r[/tex] са нечетни прости числа.Поради [tex]p|q^{r}+1,q|r^{p}+1, r|p^{q}+1,[/tex] то [tex]p,q,r[/tex] са две по две различни.
Б.о.о. ще считаме, че [tex]p=max(p,q,r)\Rightarrow p>max(q,r).[/tex] Имаме [tex]q^{r}\equiv -1(mod(p))\Rightarrow q^{2r}\equiv 1(mod(p)).[/tex] От малката теорема на Ферма имаме, че [tex]q^{p-1}\equiv 1(mod(p)).[/tex]
Нeka [tex]\delta [/tex] е показателя на [tex]q[/tex] по модул [tex]p.[/tex] Тогава [tex]q^{\delta}\equiv 1(mod(p)), \delta|p-1,\delta|2r[/tex].Понеже [tex]r[/tex] е просто и [tex]\delta|2r,[/tex] то имаме следните 4 случая:

1сл. [tex]\delta =1\Rightarrow p|q-1, p|q+1\Leftrightarrow p=2-[/tex] невъзможно.
2сл. [tex]\delta =2\Rightarrow p|(q-1)(q+1)\Rightarrow p|q+1\Leftrightarrow p=q+1,[/tex] понеже [tex]q+1\le p.[/tex] Значи [tex]p=3,q=2-[/tex] противоречие с нечетността на [tex]q[/tex].
3сл. [tex]\delta =r\Rightarrow p|q^{r}-1,p|q^{r}+1\Rightarrow p|2 \Rightarrow p=2-[/tex] противоречие с нечетността на [tex]p.[/tex]
4сл.[tex]\delta =2r\Rightarrow p|q^{2r}-1, 2r=\delta|p-1\Rightarrow p\equiv 1(mod(r)).[/tex]
Като използваме, че [tex]r|p^{q}+1, p\equiv 1(mod(r))\Rightarrow 0\equiv p^{q}+1\equiv 1^{q}+1\equiv 2(mod(r))\Leftrightarrow r|2\Rightarrow r=2- [/tex] отново противоречие с нечетността.

Така доказахме, че поне едно от числата [tex]p,q,r[/tex] е четно, б.о.о. [tex]r=2.[/tex] Поради това, че числата [tex]p,q,r[/tex] са 2x2 различни, то [tex]p,q[/tex] са нечетни.
Имаме, че [tex]p|q^{2}+1,q|2^{p}+1,[/tex] oт където получаваме, че [tex]q^{4}\equiv 1(mod(p)),2^{2p}\equiv 1(mod(q)),2^{q-1}\equiv 1(mod(q)).[/tex] Нека [tex]s[/tex] е показателя на [tex]2[/tex] по модул [tex]q.[/tex] Тогава [tex]2^{s}\equiv 1(mod(q)), \delta|q-1, \delta|2p\Rightarrow[/tex] 4 случая:
1сл. [tex]\delta =1\Rightarrow q|1 -[/tex] невъзможен случай.
2сл. [tex]\delta =2\Rightarrow q|2^{2}-1=3\Rightarrow q=3\Rightarrow p=5\Rightarrow (p,q,r)=(5,3,2) -[/tex] e решение.
3сл/4сл. [tex]\delta =p, \delta=2p\Rightarrow p|q-1\Rightarrow q\equiv 1(mod(p))\Rightarrow q^{2}\equiv 1(mod(p)).[/tex] Но [tex]p|q^{2}+ 1\Rightarrow p|2\Rightarrow p=2-[/tex]невъзможно.Окончателно, като се освободим от ограничението [tex]p=max(p,q,r)\Rightarrow (p,q,r)=(5,3,2),(2,5,3),(3,2,5)[/tex] са всичките решения на задачата.

[Titu_Andrescu]

3. Да се докаже, че ако сумата [tex]1+\frac12+\frac13+..+\frac{1}{p-1}[/tex] e представена като несъкратима дроб, където [tex]p\ge 5[/tex] e просто число, то [tex]p^2[/tex] дели числителя на тази дроб.
(Теорема на Лолстенхолм)

[Мирослав Стоенчев]

Д-во: Ще считаме, че [tex]p\ge 5[/tex] е нечетно просто число. Тогава [tex]1+\frac{1}{2}+...+\frac{1}{p-1}=(1+\frac{1}{p-1})+(2+\frac{1}{p-2})+...+(\frac{1}{\frac{p-1}{2}}+\frac{1}{\frac{p+1}{2}})=\sum_{i=1}^{\frac{p-1}{2}}(\frac{1}{i}+\frac{1}{p-i})=\sum_{i=1}^{\frac{p-1}{2}}\frac{p}{i(p-i)}=p\sum_{i=1}^{\frac{p-1}{2}}\frac{1}{i(p-i)}=\frac{p}{(p-1)!}(a_{1}+a_{2}+...+a_{\frac{p-1}{2}})[/tex]

Остава да докажем, че [tex]a_{1}+a_{2}+...+a_{\frac{p-1}{2}}\equiv 0(mod(p)),[/tex] където [tex]a_{i}=\frac{(p-1)!}{i(p-i)}.[/tex]

1сл. [tex]p=4k+1[/tex] ще използваме следната

Лема 1. Ако [tex]p=4k+1[/tex] е просто число, то броя на квадратичните остатъци по модул
[tex]p=4k+1[/tex] е [tex]\frac{p-1}{2}.[/tex]
Също така, ако [tex]s:1\le s\le p-1[/tex] е квадратичен остатък, то [tex]p-s[/tex] е също квадратичен остатък по модул [tex]p.[/tex]

Имаме [tex]a_{i}=\frac{(p-1)!}{i(p-i)}\Leftrightarrow (p-1)!=i(p-i)a_{i}\Rightarrow -1\equiv (p-1)!\equiv i(p-i)a_{i}\equiv -i^{2}a_{i}(mod(p))\Rightarrow i^{2}a_{i}\equiv 1\Rightarrow i^{2}a_{i}^{2}\equiv a_{i}(mod(p)).[/tex]
Така получихме, че [tex]a_{1},a_{2},...,a_{\frac{p-1}{2}}[/tex] са квадратични остатъци по модул [tex]p.[/tex]
Да допуснем, че за някои [tex]i,j: 1\le i<j\le \frac{p-1}{2}[/tex] имаме [tex]a_{i}\equiv a_{j}(mod(p)).[/tex] Но тогава [tex]-i^{2}a_{i}\equiv i(p-i)a_{i}\equiv (p-1)!\equiv j(p-j)a_{j}\equiv -j^{2}a_{j}\equiv -j^{2}a_{i}(mod(p))\Leftrightarrow (i^{2}-j^{2})a_{i}\equiv 0(mod(p))\Rightarrow (i-j)(i+j)\equiv 0(mod(p)),[/tex] което е невъзможно поради [tex]i-j<i+j\le \frac{p-3}{2}+\frac{p-1}{2}<p.[/tex] С това доказахме, че числата [tex]a_{1},a_{2},...,a_{\frac{p-1}{2}}[/tex] са две по две несравними по модул [tex]p,[/tex] и понеже са [tex]\frac{p-1}{2},[/tex] то те са всичките квадратични остатъци по модул [tex]p.[/tex]
Сега прилагаме Лема 1, т.е. групираме квадратичните остатъци по двойки [tex](k,p-k)[/tex] със сума [tex]p.[/tex] Тогава имаме: [tex]\left\{{a_{1},a_{2},...,a_{\frac{p-1}{2}}}\right\}[/tex][tex]=[/tex][tex]\left\{{b_{1},p-b_{1},b_{2},p-b_{2},...,b_{\frac{p-1}{4}},p-b_{\frac{p-1}{4}}}\right\}[/tex]

Следователно [tex]a_{1}+a_{2}+...+a_{\frac{p-1}{2}}=b_{1}+(p-b_{1})+b_{2}+(p-b_{2})+...+b_{\frac{p-1}{4}}+(p-b_{\frac{p-1}{4}})=\frac{p(p-1)}{4}\equiv 0(mod(p))\Leftrightarrow p|a_{1}+a_{2}+...+a_{\frac{p(p-1)}{2}}[/tex]

2сл. [tex]p=4k+3[/tex]

Лема 2. Ако [tex]p=4k+3[/tex] е просто число и [tex]s: 1\le s\le p-1[/tex] е квадратичен остатък по модул [tex]p,[/tex] то [tex]p-s[/tex] е квадратичен неостатък по модул [tex]p=4k+3.[/tex]

Използвайки Лема 2 стигаме до извода, че [tex]\left\{1,2,...,p-1\right\}[/tex][tex]=[/tex][tex]\left\{a_{1},a_{2},...,a_{\frac{p-1}{2}}\right\}[/tex][tex]\cup [/tex][tex]\left\{p-a_{1},p-a_{2},...,p-a_{\frac{p-1}{2}}\right\}[/tex]
В сила са следните равенства между множества, като елементите са разгледани по модул [tex]p=4k+3.[/tex]: [tex]\left\{a_{1},a_{2},...,a_{\frac{p-1}{2}}\right\}[/tex][tex]=[/tex][tex]\left\{a_{1}^{2},a_{2}^{2},...,a_{\frac{p-1}{2}}^{2}\right\}[/tex][tex]=[/tex][tex]\left\{(p-a_{1})^{2},(p-a_{2})^{2},...,(p-a_{\frac{p-1}{2}})^{2}\right\}[/tex],
понеже всяко от множества участващи в равенствата се състои от всички квадратични остатъци по [tex]p,[/tex] взети в някакъв ред.Следователно [tex]a_{1}+a_{2}+...+a_{\frac{p-1}{2}}\equiv a_{1}^{2}+a_{2}^{2}+...+a_{\frac{p-1}{2}}^{2}\equiv (p-a_{1})^{2}+(p-a_{2})^{2}+...+(p-a_{\frac{p-1}{2}})^{2}\equiv \frac{1}{2}[(a_{1}^{2}+a_{2}^{2}+...+a_{\frac{p-1}{2}}^{2})+((p-a_{1})^{2}+(p-a_{2})^{2}+...+(p-a_{\frac{p-1}{2}})^{2})]\equiv \frac{1}{2}(1^{2}+2^{2}+...+(p-1)^{2})=\frac{(p-1)p(2p-1)}{12}\equiv 0(mod(p))\Rightarrow p|a_{1}+a_{2}+...+a_{\frac{p-1}{2}}[/tex]

Теоремата е доказана.

[Titu_Andrescu]

4*. През 1772 г. швейцарският математик, физик и астроном Леонард Ойлер открива интересния факт, че [tex]n^2+n+41[/tex] e просто число,
когато [tex]n[/tex] e едно от числата [tex]0,1,2,..,39[/tex]. Да се докаже, че съществуват [tex]40[/tex] последователни цели числа [tex]n[/tex],
за които този полином не е просто число.

[Мирослав Стоенчев]

Д-во: Полагаме [tex]f(n)=n^{2}+n+41,p_{i}=f(i),i=0,1,...39; s=(p_{39})!; m_{i}=s+i.[/tex]
Ще докажем, че [tex]p_{i}|f(m_{i}),[/tex] за [tex]i=0,1,...,39.[/tex] Имаме [tex]f(m_{i})=(m_{i})^{2}+m_{i}+41=(s+i)^{2}+s+i+41=((p_{39})!+i)^{2}+(p_{39})!+i+41=[/tex]
[tex]=[(p_{39})!]^{2}+(2i+1)[(p_{39})!]+(i^{2}+i+41)=[(p_{39})!][(p_{39})!+2i+1]+p_{i}.[/tex]
Понеже [tex]p_{i}[/tex] е просто, [tex]p_{i}|(p_{39})![/tex] и [tex]p_{i}<(p_{39})!,[/tex] то [tex]p_{i}|f(m_{i})\Leftrightarrow f(m_{i})[/tex] е съставно.Твърдението е доказано.

[Titu_Andrescu]

5. Нека [tex]p=4k+1[/tex] е просто число. Да се докаже, че [tex]\sum_{k=1}^{p-1}\left[\frac{k^3}{p}\right]=\frac{(p^2-1)(p-2)}{4}[/tex].
(Дейвид Достър)

[Мирослав Стоенчев]

Д-во: Да разделим с частно и остатък [tex]i^{3}=t_{i}p+r_{i}; 0\le r_{i}\le p-1, i=1,2,...,p-1.[/tex] Тогава [tex]\left\[\frac{i^{3}}{p}\right\]=\left\[t_{i}+\frac{r_{i}}{p}\right\]=t_{i}\Rightarrow \sum_{i=1}^{p-1}\left\[\frac{i^{3}}{p}\right\]=\sum_{i=1}^{p-1}t_{i}=\sum_{i=1}^{p-1}\frac{i^{3}-r_{i}}{p}=\frac{1}{p}\sum_{i=1}^{p-1}i^{3}-\frac{1}{p}\sum_{i=1}^{p-1}r_{i}=\frac{1}{p}(\frac{p(p-1)}{2})^{2}-\frac{1}{p}\sum_{i=1}^{p-1}r_{i}.[/tex]

Имаме [tex] x^{3}\equiv a(mod(p))\Leftrightarrow (p-x)^{3}\equiv -a(mod(p)), [/tex] т.е.
[tex]a[/tex] е кубичен остатък по модул [tex]p\Leftrightarrow p-a[/tex] е също кубичен остатък по модул [tex]p.[/tex] Toгава [tex]\left\{r_{1},r_{2},...,r_{p-1}\right\}[/tex][tex]=[/tex][tex]\left\{p-r_{1},p-r_{2},...,p-r_{p-1}\right\}[/tex]
Следователно [tex]\sum_{i=1}^{p-1}r_{i}=\sum_{i=1}^{p-1}(p-r_{i})\Rightarrow \sum_{i=1}^{p-1}r_{i}=\frac{p(p-1)}{2}.[/tex] Накрая [tex]\sum_{i=1}^{p-1}\left\[\frac{i^{3}}{p}\right\]=\frac{1}{p}(\frac{p(p-1)}{2})^{2}-\frac{1}{p}\sum_{i=1}^{p-1}r_{i}=\frac{1}{p}(\frac{p(p-1)}{2})^{2}-\frac{p-1}{2}=\frac{(p^{2}-1)(p-2)}{4}.[/tex]
Твърдението е доказано.

[Titu_Andrescu]

6. Нека [tex]n[/tex] е естествено число. Да се докаже, че [tex]n[/tex] e просто [tex]\Leftrightarrow \underbrace{\lim}_{r\rightarrow \infty}\underbrace{\lim}_{s\rightarrow \infty}\underbrace{\lim}_{t\rightarrow \infty}\sum_{u=0}^{s}\left(1-\left(cos(\frac{(u!)^r\pi}{n})\right)^2.t\right)=n[/tex].
(Теорема на Г. Х. Харди)

[Titu_Andrescu]

7. Да се докаже, че не съществуват [tex]11[/tex] прости числа, всичките по-малки от [tex]20000[/tex], които образуват аритметична прогресия.

[Titu_Andrescu]

8. Да се намерят всички нечетни прости числа [tex]p[/tex], за които
[tex]f(p)=(2+3)-(2^2+3^2)+(2^3+3^3)-...-(2^{p-1}+3^{p-1})+(2^p+3^p)[/tex] се дели на [tex]5[/tex].
(Виетнам)

[Titu_Andrescu]

9. Две редици [tex](x_n)[/tex] и [tex](y_n)[/tex] са дефинирани по следния начин:
[tex]x_{n+1}=-2x_n^2-2x_ny_n+8y_n^2, x_1=-1[/tex],
[tex]y_{n+1}=2x_n^2+3x_ny_n-2y_n^2, y_1=1[/tex],
за [tex]n=1,2,3... [/tex] . Да се намерят всички прости числа [tex]p[/tex], за които [tex]x_p+y_p[/tex] се дели на [tex]p[/tex].
(Виетнам)

[Мирослав Стоенчев]

Задача 8. Р-е: При [tex]n=2k\in N\Rightarrow 2\equiv -3(mod(5))\Rightarrow 2^{2k}\equiv (-3)^{2k}\equiv 3^{2k}(mod(5))\Rightarrow 2^{2k}+3^{2k}\equiv 2^{2k}+2^{2k}\equiv 2^{2k+1}(mod(5)).[/tex]

При [tex]n=2k+1\in N\Rightarrow 2\equiv -3(mod(5))\Rightarrow 2^{2k+1}\equiv (-3)^{2k+1}\Rightarrow 2^{2k+1}+3^{2k+1}\equiv 0(mod(5)).[/tex] Тогава

[tex]f(p)\equiv (2^{2}+3^{2})+(2^{4}+3^{4})+...+(2^{p-1}+3^{p-1})\equiv 2(2^{2}+2^{4}+...+2^{p-1})\equiv 8(1+2^{2}+2^{4}+...+2^{p-3})\equiv 8(1+4+4^{2}+...+4^{\frac{p-3}{2}})(mod(5)).[/tex]

1сл. [tex]p=4k+3[/tex] Тогава [tex]f(p)\equiv 8(1+4+4^{2}+...+4^{\frac{p-3}{2}})\equiv (1+4+4^{2}+...+4^{2k})\equiv 8\frac{4^{2k+1}-1}{3}(mod(5)).[/tex] Но [tex]5[/tex] не дели [tex]4^{2k+1}-1,[/tex] понеже [tex]4^{2k+1}\equiv -1(mod(5)).[/tex]

2сл. [tex]p=4k+1[/tex] Имаме, че [tex]f(p)\equiv 8(1+4+4^{2}+...+4^{\frac{p-3}{2}})\equiv (1+4+4^{2}+...+4^{2k-1})\equiv 8\frac{4^{2k}-1}{3}(mod(5)).[/tex] Но [tex]5|4^{2k}-1\Rightarrow 5|f(p).[/tex]
Всички решения на задачата са простите числа от вида [tex]p=4k+1.[/tex]

[Мирослав Стоенчев]

Задача 7. Р-е: Нека [tex]p,p+d,p+2d,...,p+10d,[/tex] е аритметична прогресия съдържаща само прости числа.Тогава [tex]\gcd(p,d)=1,[/tex] в противен случай прогресията би съдържала само едно просто число.Също така случаите [tex]p=2,3,5,7,[/tex] са невъзможни, тъй като бихме получили, че числото [tex]p+kd,[/tex] за [tex]k=p[/tex] не е просто. Така показахме, че [tex]p\ge 11.[/tex]
Нека [tex]s\in \left\{2,3,5,7\right\}.[/tex] Ще докажем, че [tex]s|d, s=2,3,5,7.[/tex]
Да разгледаме числата [tex]p,p+d,...,p+(s-1)d.[/tex] Ako [tex]\gcd(s,d)=1[/tex] то числата [tex]p,p+d,...,p+(s-1)d[/tex] образуват пълна система остатъци по модул [tex]s\Rightarrow[/tex] точно едно от тях се дели на [tex]s\Rightarrow[/tex] значи не е просто.Следователно [tex]210=2.3.5.7|d\Rightarrow d=210k,k\ge 1. [/tex]

1сл. [tex]11[/tex] не дели [tex]d.[/tex] Тогава числата [tex]p,p+d,p+2d,...,p+10d,[/tex] са
[tex]11[/tex] на брой две по две несравними по модул [tex]11\Rightarrow[/tex] образуват пълна ситема остатъци по модул [tex]11,[/tex] т.е. някое от тях се дели на [tex]11.[/tex] Но [tex]p\ge 11\Rightarrow p=11.[/tex]
Да разгледаме отново числата от прогресията, които в този случай са [tex]11+j(210k), j=0,1,2,...,10.[/tex] Тогава [tex]11+j(210k)\equiv -2+2kj\equiv 2(kj-1)(mod(13)).[/tex]
Ще докажем, че при [tex]k=1,2,3,...,9[/tex] поне едно от числата [tex]11+j(210k)[/tex] се дели на 13, с което ще стигнем до противоречие, тъй като всяко от тези числа е просто и е по-голямо от [tex]13.[/tex]
Наистина при [tex]k=1\rightarrow j=1; k=2\rightarrow j=7;k=3\rightarrow j=9;k=4\rightarrow j=10;k=5 \rightarrow j=8;k=7\rightarrow j=2; k=8\rightarrow j=5; k=9\rightarrow j=3.[/tex] При [tex]k=6\rightarrow 11+210jk=11+1260=1271=31.41-[/tex] не е просто. Така доказахме, че [tex]k\ge 10\Rightarrow d=210k\ge 2100\Rightarrow p+10d\ge 11+2100.10>20000.[/tex]

2сл. [tex]11|d\Rightarrow d=210k\ge 210.11=2310\Rightarrow p+10d\ge 13+2310.10>20000,[/tex] с което твърдението е доказано.

[Titu_Andrescu]

10. Нека с [tex]s_n[/tex] означим сумата на първите [tex]n[/tex] прости числа. Да се докаже, че за всяко [tex]n[/tex] съществува цяло число, чийто квадрат лежи в интервала [tex](s_{n},s_{n+1})[/tex].

11. Да се намери най-малкото просто число, което не може да се представи като разлика на втора и трета (в произволен ред) степен на цели числа.

[Мирослав Стоенчев]

Задача 10. Д-во: Директно проверяваме, че при [tex]k=1,2,3[/tex] в интервалите [tex](s_{k},s_{k+1})[/tex] има точен квадрат.Наистина [tex]2^{2}\in (2,5)\equiv (s_{1},s_{2});3^{2}\in (5,10)\equiv (s_{2},s_{3});4^{2}\in(10,17)\equiv (s_{3},s_{4}).[/tex]
Нека при [tex]k\ge 5,[/tex] да положим [tex]m_{k}=\left\[\sqrt{s_{k-1}}\right\]+1=\left\[\sqrt{p_{1}+p_{2}+...+p_{k-1}}\right\]+1.[/tex]
Ще докажем, че [tex]s_{k-1}<m_{k}^{2}<s_{k}.[/tex] Имаме [tex]x\in R\Rightarrow x<\left\[x\right\]+1\Rightarrow \sqrt{s_{k-1}}<\left\[\sqrt{s_{k-1}}\right\]+1=m_{k}\Leftrightarrow s_{k-1}<m_{k}^{2}.[/tex]

Също така [tex]m_{k}^{2}=(\left\[\sqrt{s_{k-1}}\right\]+1)^{2}\le (\sqrt{s_{k-1}}+1)^{2}<s_{k}\Leftrightarrow s_{k-1}<\left\(\frac{p_{k}-1}{2}\right\)^{2}\Leftrightarrow p_{1}+p_{2}+...+p_{k-1}<\left\(\frac{p_{k}-1}{2}\right\)^{2}[/tex]

Последното неравенство ще докажем по индукция при [tex]k\ge 5.[/tex]
При [tex]k=5[/tex] имаме [tex]2+3+5+7=17<5^{2}=\left\(\frac{p_{5}-1}{2}\right\)^{2}.[/tex] Нека сега за някое [tex]k\ge 5[/tex] е в сила [tex]p_{1}+p_{2}+...+p_{k-1}<\left\(\frac{p_{k}-1}{2}\right\)^{2}.[/tex]
Като използваме, че [tex]p_{k+1}\ge p_{k}+2,[/tex] получаваме

[tex]\left\(\frac{p_{k+1}-1}{2}\right\)^{2}\ge \left\(\frac{p_{k}+1}{2}\right\)^{2}=\left\(\frac{p_{k}-1}{2}+1\right\)^{2}=\left\(\frac{p_{k}-1}{2}\right\)^{2}+p_{k}>s_{k-1}+p_{k}=p_{1}+...+p_{k-1}+p_{k}.[/tex]
Индукционната стъпка е направена и твърдението е доказано.