Программа государственного экзамена по математике для студентов математического факультета Московского городского педагогического университета (стр. 3 из 6)

Справедлива следующая теорема, которую приведем без доказательства.

Теорема. Еслиx=

, то

j(x)= x×

.

Следствие. Функция Эйлера вполне мультипликативна и

.

Теорема (тождество Гаусса).

.

Доказательство. Применяя основное тождество и последнее следствие, получаем, считая

,

. ÿ

4. Алгоритм Евклида и его применения

1⁰. Алгоритм Евклида. Наибольший общий делитель чисел a, b можно найти с помощью алгоритма Евклида, который состоит в следующем.

Пусть b>0. Разделим a на b, тогда по теореме о делении с остатком:

a = bq₁ + r₁.

Если r₁ = 0, то НОД(a, b) = b.

Если r₁ ¹ 0, то разделим b с остатком на r₁:

b = r₁q₂ + r₂.

Если r₂ = 0, то процесс деления закончим, а если r₂ ¹ 0, то разделим r₁ с остатком на r₂:

r₁ = r₂q₃ + r₃.

Продолжая далее таким же образом, мы закончим процесс деления кактолько получится остаток равный 0.

Заметим, что такой остаток обязательно получится. В самом деле, остаток всегда меньше делителя,поэтому b > r₁ > r₂ > r₃ > . . . и число получаемых остатков не превосходит b.

Итак, в результате указанного алгоритма получим, что:

a= bq1 + r1,
b = r1 q2 + r2,
r1 = r2 q3 + r3,	(1)
. . . . . . . . . . . . .
rn-2 = rn-1qn-1+ rn,
rn-1 = rnqn.

Тогда на основании свойств 2⁰ и 1⁰ :

НОД(a, b) = НОД(b, r₁) = НОД(r₁, r₂) = . . . = НОД(r_n-1,r_n) = r_n.

Следовательно, наибольший общий делитель чисел a и b совпадает с последним ненулевым остаткомr_nв алгоритме Евклида для чисел a и b.

Пример. Найти НОД(160, 72).

Применим к данным числам алгоритм Евклида:

160 = 72×2 + 16, 72 = 16×4 + 8, 16 = 8×2. (2)

Следовательно, НОД(160, 72) = 8.

2⁰. Теорема(о линейном представлении НОД).Еслиd - наибольший общий делитель чиселaиb, то существуют такие целые числа xиy, что выполняется равенство: d = xa + yb.

ð Допустим, что числа a и b связаны следующими соотношениями:

a= bq₁ + r₁,

b = r₁ q₂ + r₂,

r₁ = r₂ q₃ + r₃,

. . . . . . . . . . . . .

r_n-2 = r_n-1q_n-1+ r_n.

Докажем, что каждое из чисел r_k линейно выражается через a и b с целыми коэффициентами. Для r₁утверждение тривиально: r₁ = a - bq₁ . Считая, что каждое из чисел r₁, r₂, . . . , r_n-1является целочисленной линейной комбинацией чисел a и b (r_k = a_ka + b_kb), имеем

r_n = a_n-2a + b_n-2 b - (a_n-1a + b_n-1 b) q_n-1 = (a_n-2 - a_n-1) a + (b_n-2 - b_n-1 q_n-1)b. ð

Пример. Найти линейное представление НОД(160, 72).

Решение. Из второго равенства системы (2) следует, что 8 = 72 - 16×4, а из первого равенства получим, что 16 = 160 - 72×2. Из двух полученных равенств находим: 8 = 72 - 16 × 4 = 72 - (160 - 72 × 2) × 4 = (-4) × 160 + 9 × 72.

Таким образом, искомое представление НОД имеет вид:

8 = (-4) × 160 + 9 × 72.

3⁰. Связь алгоритма Евклида с непрерывными дробями. Пусть a - рациональная несократимая дробь

. Для разложения числа a в непрерывную цепную дробь можно воспользоваться алгоритмом Евклида:

Следовательно,

, откуда

Непрерывные дроби можно использовать для решения различных теоретико-числовых задач.

1. Линейное представление наибольшего общего делителя

Пример 1. Найти линейное представление наибольшего общего делителя чисел (59, 163).

Решение. Разложим в непрерывную дробь число

:

= [2; 1, 3, 4, 1, 2].

Cледовательно, можно теперь заполнить таблицу:

qs	2	1	3	4	1	2
Ps	1	2	3	11	47	58	163
Qs	0	1	1	4	17	21	59
es	+1	-1	+1	-1	+1	-1

Отсюда получаем 59 × 58 - 163 × 21 = -1 или 59 × (-58) + 163 × 21 = 1.

2. Решение линейных диофантовых уравнений

Как практически находить какое-нибудь решение линейного неопределенного уравнения

ax + by = cпри (a, b)=1, c=1 ?

Можно воспользоваться алгоритмом Евклида, из которого легко получить линейное представление НОД чисел a, b,или представить дробь

в виде последней подходящей , откуда aQ_n - bP_n = (-1)ⁿ .

Пример. Решить диофантово уравнение 163x + 59y = 1.

Решение. Мы проверили раньше, что 163 × 21 + 59 × (-58) = 1, следовательно, общее решение имеет вид:

6. Базис и размерность векторного пространства

1⁰. Линейные комбинации и линейные оболочки векторов. Выражение вида

= a₁e₁ + . . . + a_ne_n, где a_i - числа, e_i - векторы из пространства V, называется линейной комбинацией векторов e_i; числа a_i называются коэффициентами линейной комбинации.

Определение. Линейной оболочкой системы векторов E = (e₁, . . . , e_n) называется множество всевозможных линейных комбинаций векторов данной системы; обозначение L(E). Таким образом,

L(E) =

.

Заметим, что линейная оболочка системы векторов является линейным подпространством.

Говорят, что вектор vлинейно выражается через систему E, если vÎ L(E).

Отметим простейшие свойства линейных оболочек:

(а) Если W - подпространство в V, EÍW, то L(E) ÍW;

(б) Линейная оболочка L(E) совпадает с пересечением всех линейных подпространств, содержащих систему E;

(в) L(E ÈG) = L(E) + L(G), где сумма подпространств U и W определяется равенством U + W := { u + w½ uÎ U, wÎ W }.

2⁰. Линейно независимые системы.

Линейная комбинация векторов называется тривиальной, если все ее коэффициенты равны 0. Значение тривиальной линейной комбинации равно 0.

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

Заметим, что для доказательства линейной независимости системы достаточно приравнять к нулю произвольную ее линейную комбинацию и вывести из этого равенство нулю всех ее коэффициентов.

Кроме того, система векторов является линейно зависимой, если некоторая ее нетривиальная линейная комбинация равна 0.

Нам потребуются в дальнейшем следующие две леммы, которые мы приведем без доказательства.

Лемма 1. Если система E линейно независима, а система EÈs (полученная присоединением вектора s к системе E) линейно зависима, то s линейно выражается черезE.

Лемма 2 (основная лемма о линейной зависимости).

“Большая“ система линейно зависима, если она линейно выражается через “маленькую“.

3⁰. Базис линейного пространства.

Определение 1. Система E называется базисом линейного пространства V (обозначение B(V)), если выполнены условия:

(а) E линейно независима;

(б) V = L(E), т.е. всякий вектор пространства V линейно выражается через E.

Наряду с данным определением можно привести и другие эквивалентные определения.

Определение 2. Максимальная линейно независимая система E называется базисом линейного пространства V.