Архиве ознака: Теорија бројева

61. страница Диофантове Аритметике

Објављено од стране
Одговор

На 61. страници друге књиге Диофантове аритметике (издање из 1670. године; видјети на слици горе) се налази сљедећи проблем (осми по реду):

Проблем 1. Дати квадрат разложити на два квадрата.

РЈЕШЕЊЕ: Прикажимо овдје Диофантово рјешење. Он рјешава конкретан проблем, на чијем се рјешењу показује општи метод. Разложимо број 16 на два квадрата. Претпоставимо да је први број {x^2}. Тада је други број {16-x^2} такође квадрат. Други квадрат за страницу има неколико {x} – ова умањених за онолико јединица колико их има у страници квадрата 16. Нека је страница тог квадрата {2x-4}. Тада је други квадрат једнак {4x^2+16-16x} и он мора бити једнак са {16-x^2}. Додајући недостајуће за оба квадрата и избацивши из оба једнаке делове добија се да је {5x^2} једнако {16x}. На крају је {x} једнак броју {\frac{16}{5}}. Закључујемо да је један квадрат {\frac{256}{25}}, а други {\frac{144}{25}}. Сабрани дају {\frac{400}{25}} или 16, што је опет квадрат. \Box

Диофант је очигледно рјешавао проблем: „Изразити квадрат рационалног броја као збир квадрата два рационална броја.“

Нека је {b} задани рационалан број и нека је {x^2+y^2=b^2}, гдје су {x} и {y} рационална рјешења претходне једначине. Увео је смјену {y=ax-b} гдје је {a} произвољан рационалан број (као што смо видјели, користио је другачију нотацију јер у његово вријеме негативни бројеви и нула нису били познати). Датом смјеном, полазна једначина се трансформише у {b^2-x^2=a^2x^2-2abx+b^2} , односно, {2abx=(a^2+1)x^2}. Одатле је {x=\frac{2ab}{a^2+1}} и {y=b\frac{a^2-1}{a^2+1}}. Узимајући да је {b=4} Диофант је за {a=2} добио рјешења {x=\frac{16}{5}} и {y=\frac{12}{5}}.

Узимајући {b=1} и {a=\frac{m}{n}}, послије пар трансформација добијамо: {(m^2-n^2)^2+(2mn)^2=(m^2+n^2)^2}. Добили смо опште рјешење {(m^2-n^2, 2mn, m^2+n^2)} једначине {x^2+y^2=z^2}, које се први пут појављује у Еуклидовим елементима (књига X, задатак 29.), тзв. примитивне Питагорине тројке ({m,n\in N}, {(m,n)=1}, {m>n}, {m} и {n} су различите парности).

Осим приказаног проблема, 61. страница поменутог издања друге књиге Диофантове Аритметике, садржи Фермаову примједбу коју је он записао на маргинама (чувена велика Фермаова теорема):

Теорема 1. (Ферма)Немогуће је да се куб напише као збир два куба, нити да се четврти степен напише као збир четвртих степена и, уопште, да се било који број који је степен већи од другог напише као збир два иста таква степена.

Уз то је дописао: „Нашао сам заиста изванредан доказ овог тврђења, али је ова маргина сувише уска да би се доказ могао смјестити.“

У савременим ознакама велика Фермаова теорема би гласила: „Ако је {n} ма који природан број већи од 2, онда не постоје природни бројеви {x}, {y} и {z} такви да је {x^n+y^n=z^n}„.

Фермаов доказ никада није пронађен. Пронађен је његов доказ за специјалан случај {n=4}.

Проблем 2. Доказати да једначина {x^4+y^4=z^4} нема рјешења у скупу природних бројева.

ДОКАЗ: Докажимо да једначина {x^4+y^4=z^2} нема рјешења у скупу природних бројева. Претпоставимо супротно, да рјешење постоји и да је {(x, y, z)} такво рјешење са минималним {z}. Један од бројева {x} и {y} је паран, а други непаран. Нека је, без смањена општости, {y} паран. {(x^2, y^2, z)} је примитивна Питагорина тројка, па постоје узајамно прости природни бројеви {m} и {n} такви да је {x^2=m^2-n^2}, {y^2=2mn} и {z=m^2+n^2}. {(x, n, m)} је такође примитивна Питагорина тројка, па постоје узајамно прости природни бројеви {u} и {v} такви да је {x=u^2-n^2}, {n=2uv} и {m=u^2+v^2}. Уврштавањем у {y^2=2mn} добијамо да вриједи {(\frac{y}{2})^2=uv(u^2+v^2)}. {uv} и {u^2+v^2} су узајамно прости јер су такви {m} и {n} тј. {u^2+v^2} и {2uv}. Њихов производ је квадрат природног броја па постоје природни бројеви {c} и {d} такви да вриједи {uv=d^2} и {u^2+v^2=c^2}. Пошто су {u} и {v} узајамно прости, на исти начин закључујемо да постоје природни бројеви {a} и {b} такви да вриједи {u=a^2} и {v=b^2}. Уврштавањем у {u^2+v^2=c^2} добијамо да вриједи {a^4+b^4=c^2}. Уређена тројка {(a, b, c)} је такође рјешење полазне једначине таква да вриједи {c^2=u^2+v^2=m=\sqrt{m^2}<\sqrt{m^2+n^2}=\sqrt{z}<z^2} тј. {c<z}, што је у контрадикцији са избором рјешења {(x, y, z)}. Специјално, једначина {x^4+y^4=(z^2)^2} нема природних рјешења, што је и требало доказати. \Box

Ова метода доказивања је позната као (Фермаова) метода бесконачног смањивања.

Партиције природних бројева

Објављено од стране
4

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

Лајбниц (Gottfried Wilhelm Leibniz) је у писму Бернулију (Jacob Bernoulli) 1674. први пут поставио питање о броју партиција {p(n)} природног броја {n}.

Примјер 1. Партиције броја 2 су 2 и 1+1 (2 партиције); броја 3 су 3, 2+1 и 1+1+1 (3 партиције); броја 4 су 4, 3+1, 2+2, 2+1+1, 1+1+1+1 (5 партиција); лако се провјери да има 7 партиција броја 5 и 11 партиција броја 6.

На основу претходног примјера могао би се извести погрешан закључак да је број партиција природног броја увијек прост. Међутим, број 7 има 15 партиција, а {15=3\cdot 5} није прост број. Још увијек није познат одговор на питање: „Да ли постоји бесконачно много природних бројева чији је број партиција прост?“

Више од пола вијека касније, 1740. године, Philippe Naudé jе послао писмо Ојлеру (Leonhard Paul Euler), у коме га је упитао да ли нешто зна о броју различитих начина на које се неки број може написати као сума међусобно различитих сабирака (питање је било споредно, у писму се распитивао о Ојлеровом недавном успјеху у сумирању реда {\sum_{k=1}^\infty \frac{1}{k^2}}). Ојлер му је послао одговор за пар седмица, правдајући се да касни(!) због ослабљеног вида. Овдје ћу да изложим један дио његовог писма, доказ сљедеће теореме.

Теорема 1. (Ојлер) Број начина на које се дати природан број може написати као сума међусобно различитих природних бројева једнак је броју начина на које се тај исти број може написати као сума непарних бројева.

Означимо број начина на које се природан број {n} може написати као сума међусобно различитих природних бројева са {R(n)} а број начина на које се природан број {n} може написати као сума непарних бројева са {N(n)}.

Примјер 2. За {n=5} имамо да је {5=4+1=} {3+2} и {5=3+1+1} {=1+1+1+1+1}; видимо да вриједи једнакост {R(5)=N(5)=3}. За {n=8} имамо да је {8=7+1=} {6+2=5+3=} {5+2+1=} {4+3+1} и {7+1=} {5+3=} {5+1+1+1=} {3+3+1+1=} {3+1+1+1+1+1=1+1+1+1+1+1+1+1}; видимо да и у овом случају вриједи једнакост {R(8)=N(8)=6}.

Да би доказали тврђење теореме, треба да покажемо да вриједи {R(n)=N(n)} за свако {n\in N}. Доказ ћемо провести у три корака.

ДОКАЗ:

Посматрајмо бесконачан производ бинома:

{P(x)=(1+x)\cdot(1+x^2)\cdot(1+x^3)\cdot(1+x^4)\cdot(1+x^5)\cdot\cdot\cdot=} {1+x^1+x^2+(x^3+x^{2+1})+(x^4+x^{3+1})+(x^5+x^{4+1}+x^{3+2})+\cdot\cdot\cdot=} {1+1\cdot x^1+1\cdot x^2+2\cdot x^3+2\cdot x^4+3\cdot x^4+\cdot\cdot\cdot}.

Јасно је да вриједи формула:

\displaystyle P(x)=1+\sum_{n=1}^\infty R(n)\cdot x^n\ \ \ \ \ (1)

 

.

Прије него што пређемо на сљедећи корак, подсјетимо се формуле за суму геометријског реда:

\displaystyle 1+a+a^2+a^3+\cdot\cdot\cdot=\frac{1}{1-a}\ \ \ \ \ (2)

 

.

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

{Q(x)=\displaystyle\frac{1}{1-x}\cdot\frac{1}{1-x^3}\cdot\frac{1}{1-x^5}\cdot\cdot\cdot\stackrel{(2)}{=} (1+x+x^2+x^3+\cdot\cdot\cdot)\cdot} {(1+x^3+x^6+x^9+\cdot\cdot\cdot)\cdot (1+x^5+x^{10}+x^{15}+\cdot\cdot\cdot)\cdot\cdot\cdot=} {(1+x+x^{1+1}+x^{1+1+1}+\cdot\cdot\cdot)\cdot(1+x^3+x^{3+3}+x^{3+3+3}+\cdot\cdot\cdot)\cdot} {(1+x^5+x^{5+5}+x^{5+5+5}+\cdot\cdot\cdot)\cdot\cdot\cdot= 1+x^1+x^{1+1}+(x^{1+1+1}+x^3)+} {(x^{3+1}+x^{1+1+1+1})+(x^5+x^{3+1+1}+x^{1+1+1+1+1})+\cdot\cdot\cdot=} {1+1\cdot x^1+1\cdot x^2+2\cdot x^3+2\cdot x^4+3\cdot x^4+\cdot\cdot\cdot}.

Јасно је да вриједи формула:

\displaystyle Q(x)=1+\sum_{n=1}^\infty N(n)\cdot x^n\ \ \ \ \ (3)

 

.

Ако покажемо да вриједи једнакост {P(x)=Q(x)}, показаћемо (на основу формула (1) и (3)) да вриједи и једнакост

\displaystyle \sum_{n=1}^\infty R(n)\cdot x^n=\sum_{n=1}^\infty N(n)\cdot x^n

из које слиједи тврђење теореме.

Покажимо сада да вриједи једнакост {P(x)=Q(x)}. Ако израз за {P(x)} посматрамо као алгебарски разломак (допишемо именилац 1), можемо да извршимо његово проширивање а након одређених алгебарских трансформација и скраћивање.

{P(x)=\displaystyle\frac{(1+x)\cdot \mathit{(1-x)}\cdot (1+x^2)\cdot \mathit{(1-x^2)}\cdot (1+x^3)\cdot \mathit{(1-x^3)}\cdot\cdot\cdot}{\mathit{(1-x)\cdot (1-x^2)\cdot (1-x^3)\cdot (1-x^4)\cdot (1-x^5)\cdot (1-x^6)}\cdot\cdot\cdot}=}

{\displaystyle\frac{(1-x^2)\cdot (1-x^4)\cdot (1-x^6)\cdot\cdot\cdot}{(1-x)\cdot (1-x^2)\cdot (1-x^3)\cdot (1-x^4)\cdot (1-x^5)\cdot (1-x^6)\cdot\cdot\cdot}=}

{\displaystyle\frac{1}{(1-x)\cdot (1-x^3)\cdot (1-x^5)\cdot\cdot\cdot}=Q(x)}

Вриједи једнакост {P(x)=Q(x)}, што је и требало доказати. \Box

Напомена 1. Чланак је написан у LaTeX -у, затим је конвертован у wordpress.com на начин који ћу описати у сљедећем чланку.

Уламова спирала, „Град и звијезде“ и Ојлеров полином

Објављено од стране
2

„Јесерак је непомично сједио у вртлогу цифара. Првих хиљаду простих бројева, изражених у бинарном систему који се користио за све аритметичке операције од открића електронских рачунара, низали су се у поретку пред њим. Бескрајне серије састављене од само два симбола, „1“ и „0“, неуморно су промицале пред Јесераковим очима, употпуњавајући низ оних бројева чија је главна особина да се могу дијелити само самим собом и јединицом. Постојала је извјесна тајанственост у вези са простим бројевима која је одувијек опчињавала човјека, и још увијек заокупља његову машту.

Јесерак није био математичар, мада му се понекад допадало да вјерује како јесте. Све што је могао да уради било је да трага по бескрајном низу простих бројева за посебним односима и правилима које би надаренији људи објединили у општије законе. Он је био у стању да пронађе како се бројеви понашају, али није умио да објасни зашто. Уживао је у томе да крчи за себе пут кроз аритметичку џунглу, а с времена на вријеме уочавао би необичности које су промакле и вјештијим истраживачима.

Поставио је матрицу свих могућих природних бројева и подесио компјутер да
ниже просте бројеве преко њене површине, што је личило на перле распоређене по пресјецима неке мреже. Јесерак је то учинио већ стотину пута, али никада ништа није открио. Међутим, опчињавао га је начин на који су бројеви што их је проучавао биле размјештени, на први поглед без икакве правилности, дуж читавог низа природних бројева. Знао је за законе дистрибуције који су већ били утврђени, али није губио наду да ће открити нешто ново.“

Артур Кларк (Град и звијезде,1956)

У својој аутобиографији ‘’Авантуре једног математичара“, Улам (Stanislaw Marcin Ulam, 1909-1984) прича о једном догађају којег се сјећа из дјетињства: ‘’Када ми је било четири године, сјећам се да сам скакао по персијском ћилиму, и сјећам се високе фигуре свог оца како ме гледа и осмјехује се. Тада сам помислио, да се он тако осмјехује јер мисли да сам ја дјетињаст, али да ја знам да су ове шаре на ћилиму занимљиве. Нисам можда дословце тако мислио, али сигуран сам да сам осјећао да знам нешто што мој отац не зна. Можда ја знам више него он.“

Тако је Улам неком приликом 1963, вјероватно досађујући се, записивао природне бројеве у квадратну спиралу.

Ulam

Убрзо након тога, у вријеме раног развоја компјутерске графике, Улам је у сарадњи са Стејном (Myron Stein) и Велсом (Mark Wells) користећи рачунар MANIAC II у Лос Аламосовој лабораторији, направио слику спирале за бројеве до 65000.

Ulam1

На слици горе (димензија 200×200) црне тачке представљају просте бројеве. Улам је примјетио да се прости бројеви налазе углавном на дијагоналама ове шаре.

Замислимо сада, да су бројеви низани у спиралу почевши од броја 41, умјесто од јединице.

Ulam41

Лако се покаже да се бројеви на дијагонали која садржи број 41 нижу по формули f_1(n)=4n^2+2n+41 у горњи десни угао а по формули f_2(n)=4n^2-2n+41 у доњи лијеви угао. Полиноме можемо записати и на сљедећи начин: f_1(n)=(2n+1)^2-(2n+1)+41 иf_2(n)=(2n)^2-(2n)+41. Видимо да ова два полинома можемо да објединимо у један полином f(n)=n^2-n+41. Ово је полином који је открио Ојлер (Leonhard Euler, 1707-1783) и даје различите просте вриједности за n=1,...,40 (генерише 40 простих бројева). Ти прости бројеви се налазе један до другог на дијагонали Уламове спирале која почиње бројем 41.

Занимљива је могућност да је Улам читао књигу „Град и звијезде“ Артура Кларка и урадио оно што писац у то вријеме није могао, уз помоћ рачунара изаткао ћилим чије су шаре прости бројеви, не би ли открио нешто ново, нешто што је Кларковом јунаку Јесераку промакло.