Числовий аналіз

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

1. Принцип математичної індукції

Складається з трьох кроків:

1) база індукції: чи виконується при Т(1)

2) припущення індукції: чи виконується при Т(k)

3) доведення індукції: чи виконується при Т(n), n=k+1

2. Подільність чисел на множині цілих чисел та його властивості

Нехай задано a,b ? Z, a,b ? 0

Говорять, що число а ділиться на число b, якщо існує ціле число q таке, що a=b*q, де а - кратне до b, b - дільник а, q - частка. Властивості:

1. a?a

2. 0?a

3. a?±1

4. a?b ^ b?c > a?c

5. a?c ^ ab?c

6. a?b ^ b?c > (a±b)?c

7. a?b ^ (a±b)?c > b?c

8. a?b ^ b?c > ab?c

9. ac?bc ^ c?0

10. a?c ^ b?d > ab?cd

11. a?c ^ b?c > (na±mb)?c

12. a?b ^ b?a > a=±b

13. a?b ^ |b|>|a| > a=0

3. Теорема про ділення з остачею

Теорема

Які б не були цілі числа а та b завжди можливо (і при тому єдиним способом) поділити а на b з остачею.

Доведення

I. Існування

1) Нехай a ? Z, a,b ? Z+

Запишемо множину всіх чисел кратних b: …(-2)b, (-1)b, (0)b, (1)b, (2)b, … З усіх чисел знайдеться лише одне число, що

2) Нехай a ? Z, a,b ? Z- Оскільки b<0, то (-b)>0. Згідно з випадком 1, ділення a на -b можливе. Існують такі цілі числа q, r ? Z, шо а=(-b)q+r

число рівняння теорема арифметика

II. Єдність (методом від супротивного)

Припустимо, що існує дві пари чисел q1, r1, q2, r2 таких, що а=bЧq1+r1, де 0<r1<b, і а=bЧq2+r2, де 0<r2<b. Звідси bЧq1+r1=bЧq2+r2. Тоді bЧ(q2-q1)=r1-r2 (*).

Оскільки b> r1?0, b> r1?0, то відповідно b=r1-r2. Тоді рівність (*) можлива лише в єдиному випадку, коли r1-r2=0, тобто r1=r2. Звідси випливає, що bЧ(q2-q1)=0. Оскількиb?0, то q2-q1=0, тобто q2=q1.

Таким чином, ми прийшли до суперечностей із вибором чисел q1, r1, q2, r2. Ця суперечність дозволяє твердити, що припущення було хибним.

Отже, теорему доведено повністю.

4. НСД і НСК двох чисел. Властивості. Алгоритм Евкліда.

I. НСД

Нехай a,b ? Z, d ? N, то d - спільний дільник a i b, коли a?d^b?d

Найбільший із спільних дільників чисел a i b наз. найбільшим спільним дільником заданих чисел. Позначення НСД(a,b) = (a,b).

Властивості:

2.

3.

II. НСК

Нехай a i b цілі числа відмінні від 0

Спільним кратним цих чисел наз. число k, якщо воно ділиться на кожне із заданих чисел

Найменшим спільним кратним чисел a i b наз. найменше із їх спільних кратних

НСК[a,b] = [a,b]

Властивості:

2.

3.

4.

III. Алгоритм Евкліда

Теорема

Для будь-яких чисел а і b одночасно нерівних 0 НСД завжди існує і дорівнює останній відмінній від 0 остачі алгоритму Евкліда

Доведення

З першого рядка рівностей маємо: (a,b) = (b, r1), (b, r1) = (r1, r2) - з другого, …, (rn-2, rn-1) = (rn-1, rn). Звідси виходить, що (a,b) = (rn-1, rn), але rn-1? rn, тому НСД= rn. Отже, і спільний дільник a і b дорівнює rn.

5. Лінійна форма представлення НСД двох чисел

Теорема(про лінійне представлення НСД)

Для будь-яких a і b є Z , є рівняння ax+by=d (1), де d=(a,b). Це рівняння завжди має розв'язки у цілих числах.

Нехай та розв'язки рівняння (1). Тоді запис a+b=d називається лінійним представленням НСД чисел a i b . Розв'язки цього рівняння можна знайти за допомогою розширеного алгоритму Евкліда.

6. Прості і складені числа. Властивості

Число p>1 є простим, якщо не має інших дільників окрім 1 і p.

Властивості:

1) Якщо просте число p ділиться націло на деяке натуральне n?1, то p=n.

2) Якщо і - прості числа ? , то не ділиться націло на і не ділиться націло на

3) Якщо НСД(n,p) ?1 то n ділиться націло на p.

4) Якщо nєN, а p- просте, то або n ділиться націло на p,або (n,p) =1

5) Якщо добуток 2-ох простих чисел a*b ділиться націло на p, то a ділиться націло на p або b ділиться націло на p.

7. Решето Ератосфена. Теорема про нескінченність множини простих чисел

Ератосфен знайшов спосіб виділення простих чисел з будь-якої скінченної послідовносіт натуральних чисел від 1 до n. Записуємо числа від 1 до n. І послідовно перевіряємо чи діляться числа на 2, 3 і т.д. послідовно викреслюючи всі числа, що діляться.У кінці всі числа якілишилися невикресленими є простими.

Теорема Евкліда: Множина простих чисел нескінченна.

Доведення від супротивного.

Припустимо, що множина просих чисел скінченна. І нехай вона вичерпується такими числами:

, - максимальне просте число.

n= *+1

n> , n-складене.

Оскільки n-складене, то воно має ділитись хоча б на 1 з чисел:

Припустимо, що n ділиться націло на

n= *+1, що ділиться націло на , отже на має ділитися і * і 1.

1 не може ділитися націло на Прийшли до протиріччя, отже наше припущення неправильне і множина простих чисел нескінченна.

8. Основна теорема арифметики

Б-я n є N, n>1 можна єдиним способом (з точністю до порядку множників) розкласти на прості множники.

Доведення

1. Існування розкладу.

Нехай n=2. Оскільки 2-просте, то для n=2 твердження теореми справедливе. Припустимо,що твердження справедливе для всіх n?2, але менші деякого n є N.

Доведемо це твердження для натурального n.

Розглянемо натуральне число n, n-просте, то теорема справедлива. Якщо n-складене, то його можна розкласти в добуток деяких чисел n= *. 1< , 1<<n

Для та твердження буде справедливим зшідно з індуктивним припущенням. =*

=*

Тоді n= * можна записати у вигляді добутку n=**

Тобто існування розкладу для довільного натурального числа доведено.

2. Єдиність розкладу.

Неай n=2 - просте число, отже його розклад єдиний.

Припустимо, що розклад на прості множники єдиний для всіх n є N, ,

Доведемо для довільного n.

Якщо n - просте, то очевидно що його розклад теж є єдиноможливим. Нехай n- складене

Припустимо, що його можна розкласти на прості множники 2-ма різними способами.

n=p1*p2*…*pi, n=q1*q2*qs

p1*p2*…*pi=q1*q2*qs

p1*p2*…*pi ділиться націло на p1 і q1*q2*qs теж має ділитися націло на

q1 ділиться націло на .

p2*p3*…*pi= q2*q3*qs

q2 ділиться націло на .

i=s

Отже, даний розклад єдиний і теорему доведено.

9. Канонічний розклад числа. Знаходження НСД та НСК двох чисел з по їх канонічному розкладу

Канонічним розкладанням натурального числа на прості множники називають таке його розкладання, коли множники записуються в порядку зростання.

(*)

Перетворення натурального числа n до вигляду (*) називається факторизацією n, а сама форма (*)- канонічна форма числа n.

Нехай маємо два числа

Тоді НСД цих чисел (а,b)= =min()

НСК цих чисел: [a,b]= =max()

10. Скінченні ланцюгові дроби. Представлення раціонального числа у вигляді скінченного ланцюгового дробу

Якщо а- раціональне, то існує такий раціональний нескоротний дріб a/b, що a=a/b b>0. Тоді зазначений процес скінчений і його можна здійснити за допомогою алгоритму Евкліда.

a=b+; b=+… =+; =

a/b=+; b/=+… =+; =

a/b= +

11. Підхідні дроби, їх властивості. Застосування ланцюгових дробів.

Дроби р0/Q0=q0/1, р1/Q1=q0+1/q1, р2/Q2=q0+,…,

Назив підхідними дробами. При цьому назив підхідним дробом к-го порядку. Якщо к- парне, то дріб назив дробом парного порядку, і навпаки.

Властивості

1. PsQs-1-Ps-1Qs=(-1)s-1, s>=1

2. Кожен підхідний дріб нескоротний

3. PsQs-2-Ps-2Qs=(-1)s, s>=2

4. Підхідні дроби парного порядку даного ланц дробу утв зростаючу послідовність, а підхідні дроби непарного порядку - спадну послідовність

5. Кожний підхідний дріб парного порядку даного ланц дробу менший за будь-який підхідний дріб непарного порядку цього ланц дробу

Застосування

1. Розвязання конгруенцій 1 степеню.

Розвязок конгруенцій ах?b (mod m), знаходять за формулою х?(-1)n*Pn-1*b (mod m), де Pn-1-чисельний передостаннього підхідного дробу у розкладі m/а в ланц дріб

2. Розвязання діофантових рівнянь. Загальний розвязок у цілих числах рівняння ax+by=c, де a,b,c-цілі числа, а (а, b)=1, можна подати у вигляді

х?(-1)n-1*cQn-1+bt (mod m)

y?(-1)n*cPn-1-at (mod m),

де t- довільне ціле число, а Pn-1 і Qn-1 - чисельник і знаменник передостаннього підхідного дробу розкладу числа а/b у ланц дріб

3. Скорочення дробів

12. Числові конгруенції, їх властивості

Означення. Два цілих числа а і b називаються конгруентними за модулем m, якщо числа а і b при діленні на m дають однакові остачі.

Конгруентність чисел а і b за модулем m рівнозначна:

а) рівності а = b+mk, де k=0, ± 1, ± 2, ... ;

б) подільності а-b на m; тобто, а-b ділиться націло на m

в) числа а і b при діленні на m дають однакові остачі.

Властивості числових конгруенцій

1. Відношення конгруентності за даним модулем m є бінарним відношенням еквівалентності

а?а (mod m),

а? b(mod m),- b?а (mod m),

а?b (mod m), ? b?c (mod m), > а?c (mod m).

Класи еквівалентності називаються класами лишків за даним mod m.

2. а?b (mod m), ? с? d (mod m), то

а±c ? b±d (mod m)

а*c ? b*d (mod m)

3. а?b (mod m) > а+c ? b+c (mod m).

4. а?b (mod m) > а*c ? b*c (mod m).

5. а?b (mod m) > а ? b+mt (mod m), t€Z.

6. а*k ? b*k (mod m), (k,m) = 1 > а ? b (mod m).

7. (k,m) = d ? а*k ? b*k (mod m) > а ? b (mod m).

8. а?b (mod m) > а*k ? b*k (mod m*k)

9. Якщо а?b (mod m1) ? а?b (mod m2) > а?b (mod [m1,m2])

10. а?b (mod m) ? m?d > а?b (mod m)

11. а?b (mod m) > (a,m)= (b,m)

12. а?b (mod m) ? a?d ? m?d > b?d

13. а?b (mod m) > аn?bn (mod m)

14. а?b (mod m) ? p(x) - многочлен з цілими коеф степеня m > p(а) ? p(b) (mod m)

15. Якщо у виразі f(a1,a2,..,ak)= усі коеф числа А і числа а1,а2,…,аk замінити на конгруентні їм за mod m коеф В i b1, b2,..,bk, то вираз g(b1,b2,..,bk)= буде конгруентний заданому за модулем m.

13 Класи лишків за модулем. Властивості. Повна та зведена система лишків

а?b (mod m) - (a-b) ? d

1. а?а (mod m),

2. а? b(mod m),- b?а (mod m),

3. а?b (mod m), ? b?c (mod m), > а?c (mod m).

Відношення еквівалентності розбиває множину цілих чисел на m класів еквівалентності. Класом лишків по (mod m) назив клас (множина) цілих чисел, що дають при діленні на m одну і ту ж остачу. Позначають .

= {mq+a | q€Z}

= {mq+0 | q€Z}

= {mq+1 | q€Z}

= {mq+(m-1) | q€Z}

Властивості класів лишків

1. = > а?b (mod m).

2. ? = ? - b?/а (mod m), (не когруентне)

3. класу лишків назив лишком по відношенню до інших представників цього класу.

Лишок, найменший за абсолютною величиною назив абсолютним найменшим лишком. Множина класів познач Zm={}

Узявши від кожного класу по одному лишку, ми отримаємо повну систему лишків по mod m.

Основні системи

1. повна система найменших невід'ємних лишків: 0,1,…,m-1

2. повна система найменших додатних лишків: 1,2,…,m

3. повна система найменших за абсолютною величиною лишків:

· m-парне; +1, …., -2, -1, 0,

· m-непарне; +1, …., -2, -1, 0, 1, …,

Властивості:

1. Будь-які м чисел, які попарно неконгруентні за mod m, утворюють повну систему лишків.

2. Якщо а і м взаємно прості і у виразі ах+b, де в-ціле, х пробігає усі значення повної системи лишків за мод м, то ах+b теж набуває усіх значень з повної с-ми лишків.

3. Якщо з кожного класу лишків взяти по 1 числу, взаємно непростому з mod m, то отримаємо зведену систему лишків.

4. Над класами лишків можна виконувати операції додавання (віднімання) та множення.

16. Конгруенції з одним невідомим розв'язання. Розв'язання конгруенцій. Рівносильні конгруенції.

Конгруенції з одним невідомим розв'язання.

(Алгебраїчною) конгруенцією з одним невідомим називають конгруенцію виду:

Якщо не кратне , то - степінь коренів.

Розв'язання конгруенцій.

Розв'язати конгруенцію означає знайти всі такі , що задовольняють цю конгруенцію, або довести, що конгруенція розв'язків не має.

Розв'язком конгруенції (1) є клас лишків за модулем , кожне число якого задовольняє цю конгруенцію. Конгруенція (1) має стільки розв'язків, скільки класів лишків її задовольняють.

Рівносильні (еквівалентні) перетворення, що не порушують множину розв'язків конгруенції:

· Додавання до обох частин конгруенції будь-якого многочлена із цілими коефіцієнтами.

· Додавання до однієї частини конгруенції многочлена з коефіцієнтами кратними модулю.

· Множення/Ділення обох частин конгруенції на число взаємно просте з модулем.

· Множення обох частин конгруенції та модуля на натуральне число.

Рівносильні конгруенції.

Дві конгруенції називають рівносильними (еквівалентними), якщо розв'язок однієї з них є розв'язком іншої.

17. Конгруенції І степеня. Теорема про існування та число розв'язків конгруенції 1-го степеня

Конгруенції І степеня.

Конгруенція виду , де не кратне називається конгруенцією першого степеня з одним невідомим.

Теорема про існування та число розв'язків конгруенції 1-го степеня.

Нехай , тоді:

· Якщо не кратне , то конгруенція (2) розв'язків не має.

· Якщо , конгруенція (2) має єдиний розв'язок, який знаходять за формулою (метод Ейлера).

· Якщо і кратне , то конгруенція (2) має -розв'язків. Всі ці розв'язки утворюють один клас по модулю .

18. Методи розв'язання конгруенцій І степеня

I. Метод спроб.

Підстановка в конгруенцію (2) чисел повної системи лишків за модулем (доцільно брати повну систему найменших за абсолютною величиною лишків).

Доцільно використовувати при невеликих модулях.

II. Метод елементарних перетворень (штучний метод).

Конгруенція (2) за допомогою елементарних перетворень зводиться до рівносильної їй конгруенції з коефіцієнтом при рівним одиниці.

III. Метод Ейлера.

Базується на використанні формули , де - функція Ейлера. Працює, коли .

IV. Метод застосування лишків.

Розв'язок конгруенції (2) знаходять за наступною формулою:

, де - клас лишків, обернений до ; .

V. Метод застосування ланцюгових дробів.

Розв'язок конгруенції (2) знаходять за формулою , де - чисельник передостаннього підхідного дробу у розкладі в ланцюговий дріб.

19. Системи лінійних конгруенцій, методи розв'язання. Китайська теорема про лишки

Системою лінійних конгруенцій з одним невідомим називається система виду:

Розв'язком системи є таке число є Z, яке задовольняє усі конгруенції системи.

Якщо числа m1, m2, … , mk попарно взаємно прості, то має місце Китайська теорема про лишки:

М = m1 m2 … mk, а числа y1, y2, … , yk підібрані таким чином, що:



Тоді існує єдиний розв'язок

де .

У загальному випадку для розв'язку конгруенції необхідно з першої конгруенції виразити . Це значення підставляють у 2-ге рівняння системи і розв'язують відносно . Використовуючи результат виражений через та попередньо отриманий вираз , виражають тепер через . Цей процес повторюється доти, поки не буде виражено через останнє рівняння системи.

20. Конгруенції 2-го степеня. Квадратичні лишки та нелишки. Критерій Ейлера.

Конгруенцію другого степеня виду :

необхідно звести до виду

де

Якщо конгруенція має хоча б один розв'язок, то - квадратичний лишок за , у протилежному випадку - квадратичний нелишок за .

Критерій Ейлера: для будь-якого непарного простого модуля число є квадратичним лишком за тоді і тільки тоді, коли , і квадратичним нелишком, коли .

21. Символи Лежандра та Якобі. Властивості та обчислення.

Символ Лежандра визначається рівністю:

Властивості:

1. Якщо ;

2. ;

3. ;

4. ;

5. ;

6. ;

7. ;

8. ;

9. Якщо і - різні непарні прості числа, то

Узагальненням символу Лежандра є символ Якобі , де є розкладом із простих множників, що утворює добуток із символів Лежандра.

22. Діофантові рівняння

Діофантовим рівнянням є рівняння із цілими коефіцієнтами, розв'язки якого шукаються на множині цілих чисел Z.

Найпростішие діофантове рівняння має вигляд: , для якого потрібно вказати усі можливі цілі розв'язки.

З рівняння отримаємо, що . Знайшовши частинні розв'язки, отримаємо загальний розв'язок рівняння:

Размещено на Allbest.ru