Системы линейных уравнений. Разрешимость систем линейных уравнений. Методы решения.

Пусть дано Р – числовое поле, х₁, х₂, …, х_n – переменные из поля Р. Предикат от n переменных а₁x₁ + а₂x₂+ …+ а_nx_n = b, где а₁, а₂, …, а_n, bÎP, называется линейным уравнением с n неизвестными над полем Р. Упорядоченная n-ка чисел a=<a₁, a₂, …, a_n>, a_iÎP, говорят является решением линейного уравнения , если она обращает его в истинное высказывание: a₁x₁ + a₂x₂+ …+ a_nx_n = b.

Системой линейных уравнений будем называть непустое конечное множество линейных уравнений. Системой линейных уравнений называется конъюнкция линейных уравнений. Решением системы ЛУ называется любая упорядоченная n-ка чисел, являющаяся решением каждого уравнения данной системы. Если система ЛУ имеет хотя бы 1 решение, то ее называют совместной. Если множество решений системы пусто, то ее называют несовместной. Решение СЛУ методом Гаусса: метод последовательного исключения неизвестных. Пусть имеется система S и ставится задача: найти множество ее решений. С помощью элементарных преобразований преобразуем систему S в систему, которая легуо решается. 1 ШАГ: если в системе S имеется уравнение вида 0=0, тогда его отбрасываем и будем считать, что в системе S таких уравнений нет. Если система S имеет уравнение вида 0=b, то поскольку не одна n-ка чисел не может удовлетворять этому уравнению, то эта система S несовместна. Предположим, что в системе нет уравнений вида 0=b. Рассмотрим коэффициенты первого уравнения системы. Хотя бы один из них отличен от 0. Перенумерацией неизвестных добьемся того, чтобы этот коэффициент встал на первое место. Будем считать, что а₁₁¹0. Исключим неизвестное х₁ из всех уравнений, начиная со второго. Умножим первое уравнение системы на (-а₂₁/a₁₁) и сложим со вторым. Получим систему S₁. Уравнения вида 0=0 отбрасываем, если есть уравнения 0=b, то система несовместна. 2 ШАГ: аналогично предыдущему шагу исключим из всех уравнений, начиная с третьего переменную х₂. Дальнейшие шаги выполняем аналогично и может оказаться, что на каком-то шаге получим уравнение вида 0=b, тогда система S несовместна, или через конечное число шагов мы придем к системе S*:

 a₁₁x₁ + a₁₂x₂+ …+ a_1nx_n = b₁

        a¢₂₂x₂+ …+ a¢_2nx_n = b¢₂

_{………………………………………………}

             a*_ssx_s+ …+ a*_snx_n = b*_s.

где s£m.

В системе S* имеем a₁₁¹0, a¢₂₂¹0, …, a*_ss¹0. Такую систему называют ступенчатой, а в случае s=n – треугольной, тогда: а_nn*x_n=b*_n. Она всегда совместна и имеет единственное решение, которое находится по формуле x_n=b*_n/а*_nn. Подставим переменную х_n в предпоследнее уравнение, найдем значение х_n-1. И т.д., поднимаясь выше к первому уравнению, найдем значение переменной х₁. Эта упорядоченная n-ка будет единственным решением системы. Предположим, что s<n у системы S*. Тогда неизвестные х_s+1, x_s+2, …, x_n объявим свободными и будем им придавать произвольные значения: х_s+1= a_s+1, x_s+2=a_s+2, …, x_n=a_n. Подставим эти значения в систему S*. Она преобразуется в треугольную относительно s неизвестных. Согласно предыдущим рассуждениям треугольная система имеет единственное решение: (a₁, a₂, …, a_s). Тогда решением исходной системы будет: (a₁, a₂, …, a_s, a_s+1, …, a_n). Система S* в этом случае будет иметь бесконечно много решений, поскольку свободным переменным можно придавать любые значения. Решение, которое зависит от свободных переменных, называется общим решением системы. Теорема: Метод Гаусса – метод последовательного исключения неизвестных – применим к любой СЛУ, при этом система будет несовместна, если в процессе преобразований мы получим кравнение вида 0=b. Если же такого уравнения мы не встретим, то система будет совместной. И она будет иметь единственное решение, если она приводится к треугольному виду, и иметь бесконечно много решений, если она приводится к ступенчатому виду.

ЛУ называется однородным, если свободный член =0. СЛУ, состоящая из однородных уравнений, называется однородной СЛУ. Такая система всегда совместна, т.к. ее решением всегда является нулевое решение. Теорема: если в однородной СЛУ число уравнений < числа неизвестных, то эта система имеет бесконечно много решений.

Теорема Кронекера – Капелли (критерий совместности СЛУ): СЛУ совместна Û ранг основной матрицы равен рангу расширенной.

Метод Крамера: Теорема: пусть имеется система из n ЛУ с n неизвестными. Если определитель основной матрицы не равен 0, то система имеет единственное решение, которое находится по формулам: х₁=|А₁|/|А|, х₂=|А₂|/|А|, …, х_n=|А_n|/|А|, где А_i получается из матрицы А заменой i-того столбца столбцом свободных членов. Этот метод сложнее, чем метод Гаусса и применяется реже, когда определитель ¹0.

Матричный способ: пусть имеется СЛУ:

    a₁₁х₁ + a₁₂х₂ + … + a_1nx_n = b₁,

    ………………………………….

    a_n1х₁ + a_n2х₂ + … + a_nnx_n = b_n.

                  a₁₁, a₁₂, …, a_1n

      A=       …………………

                  a_n1, a_n2, …, a_nn

                 x₁

     X=  …

                 x_n

                 b₁

     B = ….

                 b_n

AX=B – матричное уравнение. Запись СЛУ в этом виде называется записью в матричной форме.

AX=B |×A^-1

A^-1AX=A^-1B

EX=A^-1B

X=A^-1B.

Столбец неизвестных можно найти путем умножения обратной основной матрицы на столбец свободных членов. Этот способ пригоден только в том случае, если для основной матрицы существует обратная.

1. Кольцо целых чисел. Отношение делимости. Простые числа. Бесконечность множества простых чисел. Основная теорема арифметики.

Кольцо целых чисел.

N-множество натур. чисел(1,2,3…). Z-множество цел. чисел(…-1,0,1…).Целое число a делится нацело на b≠0, если $ такое qÎZ, что выполняется a=bq, q-частное, b-делитель, a-делимое.

Свойство отношений делимости. 1. Отношение делимости почти рефлексивно ("aÎZ)(a≠0)(a:a). 2. Отношение делимости транзитивно. (a:b)Ù(b:c)®(a:c). Д-во: т.к a:bÞ$ qÎZ, a=bq; b:cÞ$ tÎZ, b=ct; a=(ct)q=c(tq), tqÎNÞ a:c. 3. Отношение делимости сохраняется при изменение знаков делимого и делителя. a:b®(-a:b)Úa:(-b)Ú (-a):(-b). 4. Если a:cÙb:c®(a±b):c. Д-во: a:cÞ$ qÎZ, a=cq; b:cÞ$ tÎZ, b=ct; a±b=cq±ct=c(q±t), (q±t)ÎN. 5. Если a:cÙbÎZ, то ab:c. 6. Если a:cÙbне:c®(a±b)не:c. Д-во:метод от противного. Представим (a+b):c, тогда $qÎZ, что (a+b)=cq, по условию a:cÞ$tÎZ, что a=ct, ct+b=cq, b=cq-ct=c(q-t), (q-t)ÎNÞb:c.Пришли к противоречию,Þbне:c.7. 0 делится на " число b. 8. " число a:1. 9. Если а≠0, то не$ такого целого числа q, что 0q=а. Это свойство исключает деление числа на 0. 0q=0, "qÎZ, поэтому 0:0 неопределенно однозначно, деление на 0 невозможно. 10.a:bÙa≠0®|a|>=|b|.Д-во: Пусть a:bÞ$qÎZ, что a=bq, т.к a≠0, то q≠0 |a|=|bq|, то |q|>=1 |a|=|b||q|Þ1) |q|=1, тогда |a|=|b|, 2) |q|>1, тогда |a|>|b|.

Простые и составные числа.Натур. число p наз-ся простым, если оно >1 и не имеет положительных делителей отличных от 1 и p. Натур. число n наз-ся составным, если оно >1, и имеет по крайней мере 1 положит. делитель отличный от 1 и n. Если n-составное число, то $dÎN, что n=n1d, 1<n1<n, 1<d<n. 1 не явл-ся ни простым, ни составным числом. Среди прост-х чисел $ 1 четное простое число, остальные нечетные. Множ-во всех N чисел можно разбить: простые, составные, число 1. Основной теоремой арифметики явл-ся теорема, которая гласит: что " состав-е число единст. образом расклад-ся на сомножители. Св-ва прстых чисел: Т1: Если простое число p:n, где nÎN, n≠1, то p=n. Д-во: МОП. Пусть p≠n, p-простое числоÞp:1Ùp:pÞp≠nÞn=1, а по усл. n≠1. Пришли к противоречию. Т2: Если p1, p2 различные простые числа, то p2 не делится на p1. Т3: Всякое nÎN, n>1 делится на какое-либо простое число. Т4: Если nÎN, а p-простое число, то либо n:pÚ(n,p)=1. Т5: Если произ-е 2-х или нескольких N чисел делится нацело на простое число p, то хотя бы 1 из сомнож-й делится нацело на p. T6: Если nÎN-составное, а p-его найм. простой делитель, то p£Ön. Д-во: Т.к n-составное число, а p-наим. простой делитель p£Ön, p£n1. Умножим левую и правую части неравенства на равные числа на pn1 и n. p²n1£n1n, откуда p²£nÞ p£Ön.Следствие: если n не делится нацело ни на одна простое число не превосход-го Ön, то n-простое число, в противном случае составное. Основная теорема арифметики.Если nÎN, n>1, то оно либо просто, либо может быть представлена и притом единст. образом в виде произведения простых чисел. Д-во: 1)Докажем $ разложения числа на простые сомножители. Метод мат. индукции. а)пусть n=2, n-простое число. б)пусть утвер-е теоремы справедливо для " N чисел 2£N<n. Расмот-м nÎN. 2случая:1.n-простое число. 2.n-составное число, n=n1n2, где 1<n1<n, 1<n2<n, по предположению теорема справедлива. n1=p1p2…pi, n2=p_i+1p_i+2…p_k. n=p1p…pi…pk(1). Это доказывает предположение. 2)Единственность: МОП: пусть представление(1) не единственно. ММИ: а). n=2, n-простое число б)пусть теорема верна для " N чисел 2£N<n. Расмот-м nÎN. 2случая:1.n-простое число. 2.n-составное число, n=n1n2, где 1<n1<n, 1<n2<n, для чисел n1 и n2 разлож-е на простые сомнож-и един-о. Пусть n можно представить: n=p1p2…pk, n=q1q2…qsÞ p1p2…pk=q1q2…qs(2). Левая часть делится на p1, значит и правая делится на p1, т.к. q1,q2,…qs-явл-ся простыми числами, то деление на p1 возможно в том случае когда 1 из сомножителей =p1, p1=q1. (p2…pk)<n=(q2…qs)<n(3). По индукции из рав-а (3) следует k=s. Произведение p2…pk и q2…qs отлич-ся лишь порядком расположения сомножителей. Т.о. перенумеровав в соотв-м порядке, получим: p2=q2, p3=q3…pk=qs. Т.о. мы получли , что разложение числа n на простые сомножители ед-о. Бесконечность мн-ва простых чисел.Теорема Евклида: Мн-во простых чисел бесконечно. Д-во: МОП: пусть множество простых чисел конечно: p1=2, p2=3, p3=5,…pk. pk-наиб. простое число, составим произведение: p1p2…pk. Расмот-м nÎN, n=p1p2…p_k+1, т.к. n>pk, то n-составное число, тогда оно должно делится на простое число, а т.к. простые числа образ-т мн-во { p1,p2,…pk }, то n делится хотя бы на 1 из этих чисел. Пусть n:p1, т.к. n=p1p2…p_k+1:p1, тоÞ1:p1>1, а этого быть не может. Мн-во простых чисел бесконечно. Теорема: Об интервалах. $ интервалы, не имеющие ни одного простого числа. Д-во: Возьмем nÎN и составим послед-ть чисел: (n+1)!+2, (n+1)!+3, (n+1)!+4, (n+1)!+(n+1). (n+1)!+2:2, (n+1)!+3:3, (n+1)!+4:4, (n+1)!+(n+1):(n+1), Þ все эти n чисел составные. Решето Эратосфена: Суть: Выписыв-ся все числа, затем вычерк-м 1, затем все числа кратные 2, кроме 2. Вычеркиваются до тех пор, пока не получили бы Ön. Схема решета Эратосфена: Каждое число кратное ps следующее за ps необходимо вычеркнуть, дойдя до невычеркнутого простого числа ³Ön следует остан-ся, поскольку все невычеркнутые числа явл-ся простыми.

1. Числовые сравнения и их свойства. Теоремы Эйлера и Ферма. Линейные сравнения с одним неизвестным. Методы решения.

Опр: а,bÎZ называются сравнимыми по модулю |m|, если их разность делится на m ((a-b)¶m). аºb(mod m) – число а сравнимо с числом b по модулю mÛ(a-b)¶m. Пр: m=3, 8º5(mod 3). Теорема: (признак сравнимости 2-х чисел): 2-а числа a и b сравнимы по модулю m Û когда a и b имеют одинаковые остатки при делении на m. Св-ва сравнения: 1группа (независят от модуля): 1)отношение сравнения явл-ся отношением эквивалентности: а)рефлексивно аºа(mod m) б)симметрично аºb(mod m)® bºа(mod m) в)транзитивно аºb(mod m) Ù bºс(mod m) ® аºс(mod m).

2)сравнения по одному и тому же модулю можно почленно складывать. Д-во: пусть аºb(mod m) Ù сºd(mod m); а+сºb+d(mod m)-? a-b=mg, c-d=mt, где g,tÎZ. Сложим 2 равенства: (a+c)-(b+d)=m(g+t), а+сºb+d(mod m).

3) 2 сравнения по одному и тому же модулю можно почленно вычитать одно из другого.

4)к обеим частям сравнения можно прибавить одно и тоже Z число. Д-во: аºb(mod m); ); а+сºb+с(mod m)-? a-b=mg, где gÎ Z, сºс(mod m) ®по св-ву (2) сложим: а+сºb+с(mod m). След-е: члены сравнений можно переносить из одной части в другую, с противоположным знаком.

5)сравнения по одному и тому же модулю можно перемножать. След-е: обе части сравнения можно возводить в одну и туже Z неотрицательную степень.

6)обе части сравнения можно умножать на одно и тоже Z число.

2 группа (зависящие от модуля): 7) аºb(mod m) и m¶n, то аºb(mod n). Д-во: т.к. ºb(mod m), то (a-b) ¶ m и по условию m¶n (по транзитивности) (a-b) ¶n Þ аºb(mod n).

8)Обе части сравнения и модуль можно умножить на одно и тоже Z положительное число. Д-во: аºb(mod m), с>0,cÎZ; a-b=mg, умножим обе части на с: ac-bc=mcg. По определению сравнения Þ асºbс(mod mс).

9)если akº bk(mod m), (k,m)=d,то аºb(mod m/d). Д-во: d=(k,m), k=k₁d, m=m₁d. akº bk(mod m) Þ (ak-bk)¶ m Þ k₁d (a-b)¶ m₁d Þ (по св-вам отношения делимости) (a-b) k₁¶ m₁. Т.к. (k,m)=1 Þ (a-b)¶ m₁ Þ аºb(mod m₁), т.е. (mod m/d). чтд. След-е: 1.если d=k и m¶k, из того, что akº bk(mod m) Þ aº b(mod m/k). 2.если d=1, т.е. (k,m)=1, то из того, что akº bk(mod m) Þ aº b(mod m). Обе части сравнения можно разделить на их общий делитель взаимнопростой с m не меняя модуля. Пр: 60º 9(mod 17), 60¶3 и 9¶3, (3,17)=1, то 20º 3(mod 17). Замечание: делить обе части сравнения на одно и то же не взаимнопростое с модулем число нельзя (вообще говоря), т.к. после деления могут получиться числа не сравнимые по данному модулю. Пр: 8º 4(mod 4) |¶4 , : 2 неº 1(mod 4).

Классы вычетов по данному модулю: Опр: говорят, что 2-а числа aÙb Î 1-му и тому же классу вычетов по mod m, когда (a-b) ¶m. Все числа Î 1-му и тому же классу вычетов по mod m имеют одинаковые остатки при делении на m. Поэтому можно обозначить классы вычетов с помощью этих остатков. При делении на m возможны остатки 0,1,2,…,m-1. Чтобы отличить классы вычетов от остатков, будем ставить черту. Т.о. класс вычетов 0 – состоит из чисел кратных m; 1 – состоит из чисел, которые при делении на m дают в остатке 1, ну и т.д. Из определения сравнения по mod m, получаем, что xÎZ Î классу вычетов а по mod m, в том и только том случае, когда x=a+mt, где tÎZ, т.е. когда xºa(mod m). Пр: пусть m=2. При делении на 2 возможны 2 случая: 0 и 1. 0 – все четные числа, 1- все нечетные числа. Чтобы сложить классы вычетов a и b по mod m, нужно взять из класса а элемент, а из b – b и их сложить.

Полная система вычетов. Выберем из каждого класса вычетов по mod m по одному и тому же числу. Получим m целых чисел: x₁,x₂,…,x_m. Множество { x₁,x₂,…,x_m} – полная система вычетов по mod m. Т.к. каждый класс вычетов содержит бесконечное множество элементов, то полное число вычетов бесконечно.

Пр: составим полную систему вычетов по mod m=2: 0={…-2,0,2…}; 1={…-3,-1,1…}. (0,1) – ПСВ, (2,3) – ПСВ.

Св-ва ПСВ:1. любую совокупность m – целых чисел x₁,x₂,…,x_m (1) попарно не сравнимых по mod m образуют полную систему вычетов по mod m. Д-во: 1)любое из чисел совокупности 1-го Î некоторому классу вычетов по mod m. 2)любая пара (x_i,y_j), где i¹j, i,j=1,…,m из совокупности (1) несравнимы между собой, т.е. представляют собой не сравнимые по mod m числа (из усл.), т.е. Î различным классам вычетов. 3)число вычетов в совокупности (1) равно m, т.е. ровно столько, сколько содержит ПСВ по mod m.

2.Пусть (a,m)=1, b – произвольное Z число, тогда если x₁,x₂,…,x_m явл-ся ПСВ по mod m, то ax₁+b, ax₂+b,…,ax_m+b (2) – также явл-ся ПСВ по mod m.