Към съдържанието

Viva Cognita at Facebook
Viva Cognita at Twitter
Viva Cognita at YouTube




Снимка

НОД и теоремата на Безу

Публикувано от YanitsaPehova , 17 октомври 2014 · 3402 видяно

В училище НОД винаги се дефинира чрез израза "най-голям общ делител" (от каквото е съкращение НОД), а в извънкласната подготовка понякога се споменава т. нар. теорема на Безу:

Нека a,b\in\mathbb{Z}\backslash\{0\} и нека d=НОД(a,b ). Тогава съществуват x,y\in\mathbb{Z}, такива че

ax+by=d.


В теорията на числата обаче често НОД се дефинира като минимума на израза ax+by, където x и y са цели числа, вместо като максималното число, което дели едновременно a и b. Основната причина зад това е че не знаем дали такова максимално число е еднозначно дефинирано (това може да ви се струва странно, но в числови множества, малко по-сложни от естествените числа, някои от тези очевидни неща не са верни).

Естественият ред на дефиниции около понятието НОД е следният:
  • Нека (a,b )=\min\{ax+by:x,y\in\mathbb{Z}\} е НОД-ът на a и b.
  • Тогава ако n|a и n|b, то n|(ax+by) за всички x,y\in\mathbb{Z}, в частност дели НОД-а (a, b ). Това ни казва, че всеки общ делител на a и b дели и НОД-а им.
  • Всичко това се случва обаче преди да знаем какво е просто число. Дефинираме просто число като число, което се дели само на 1 и на себе си.
  • След това имаме всичко нужно, за да докажем, че за просто число p имаме p|ab\Rightarrow p|a или p|b. Обърнете внимание, че този факт следва директно от горното твърдение само ако знаем, че всяко число се разлага на прости множители, но това все още не ни е известно. Обаче можем да го докажем като забележим, че ако (p,a)=1, т.е. p\not|a, то от дефиницията на НОД px+ay=1 за x,y\in\mathbb{Z}; тогава ако умножим това равенство по b, получаваме pbx+aby=b\Rightarrow p|b.
  • След като сме се сдобили с това, можем да докажем фундаменталната теорема на аритметиката, а именно че всяко естествено число се разлага на прости множители по единствен начин. Накратко, ако n не е просто, го пишем във вида n=n_1n_2, ако от двата множителя някой не е прост, разделяме и него на две, и т.н. Горното твърдение използваме когато започнем да доказваме, че не може да имаме две различни разлагания p_1^{\alpha_1}...p_k^{\alpha_k}=p_1^{\beta_1}...p_k^{\beta_k}: тъй като p_1 дели дясната страна, то можем да заключим че p_1 дели някой от множителите от дясно (p|ab\Rightarrow p|a или p|b), и един по един да изравним всички прости делители от двете страни (т.е. \alpha_i=\beta_i).
  • Тук е моментът вече, в който можем да кажем, че НОД на a=p_1^{\alpha_1}...p_k^{\alpha_k}, b=p_1^{\beta_1}...p_k^{\beta_k} е (a,b )=p_1^{\min\{\alpha_1,\beta_1\}}...p_k^{\min\{\alpha_k,\beta_k\}}. Понеже сме го написали, и двете разлагания са добре дефинирани, със сигурност знаем, че НОД съществува и също е добре дефиниран (в случая "добре дефиниран" може да се разбира като "еднозначно дефиниран").

След като сме проследили горния процес, разбираме защо не можем да дефинираме НОД еднозначно посредством разлаганията на a и b: за да имаме разлагания, имаме нужда от ФТА; за да имаме ФТА, имаме нужда от p|ab\Rightarrow p|a или p|b; за да имаме това, имаме нужда от теоремата на Безу; за да имаме теорема на Безу, имаме нужда от еднозначно дефиниран НОД. В такъв случай получаваме един вид кръгов аргумент стил A\Rightarrow B\Rightarrow C\Rightarrow A, наличието на който вдига кръвното на всеки уважаващ себе си математик.

  • 1



Август 2019

П В С Ч П С Н
   1234
567891011
12131415161718
19202122 23 2425
262728293031 

Последни публикации

Viva Cognita е партньорски проект на Института по математика и информатика на БАН, Съюза на математиците в България и VIVACOM