Презентация, доклад на тему Материалы к уроку. Теория чисел.Большая презентация.

145; 462)

2 145 = 5*429 = 5*3*143=5*3*11*13
462 = 2*231= 2*3*7*11

НОД (2 145; 462) = 33

Для начала от 1071 отнимем кратное значение 462, пока не получим разность меньше, чем 462. Мы должны дважды отнять 462, (q0 = 2), оставаясь с остатком 147:
1071 = 2 × 462 + 147.Затем от 462 отнимем кратное значение 147, пока не получим разность меньше, чем 147. Мы должны трижды отнять 147 (q1 = 3), оставаясь с остатком 21:
462 = 3 × 147 + 21. Затем от 147 отнимем кратное значение 21, пока не получим разность меньше, чем 21. Мы должны семь раз отнять 21 (q2 = 7), оставаясь без остатка:
147 = 7 × 21 + 0. Таким образом последовательность a > b > r1 > r2 > r3 > … > rn в данном конкретном случае будет выглядеть так:
1071 > 462 > 147 > 21.
Так как последний остаток равен нулю, алгоритм заканчивается числом 21 и НОД (1071, 462) = 21.

(ост. 16) 
что можно записать в виде равенства 64=48·1+16, то есть, q1=1, r1=16.
Теперь делим b на r1, то есть, 48 делим на 16, получаем 48:16=3, откуда имеем 48=16·3. Здесь q2=3, а r2=0, так как 48 делится на 16 без остатка.
Мы получили r2=0, поэтому это был последний шаг алгоритма Евклида, и r1=16 является искомым наибольшим общим делителем чисел 64 и 48.
Ответ:
НОД(64, 48)=16.

алгоритмом Евклида для нахождения НОД(432, 111).
Разделив 432 на 111, получаем равенство 432 = 111·3 + 99.
На следующем шаге делим 111 на 99, имеем 111 = 99·1+12.
Деление 99 на 12 дает равенство 99 = 12·8 + 3.
А 12 на 3 делится без остатка и 12 = 3·4. Поэтому это последний шаг алгоритма Евклида, и НОД(432, 111)=3, следовательно, и искомый наибольший общий делитель чисел 111 и 432 равен 3.
Ответ:
НОД (111, 432)=3.

НОД( 104; 42)
Найти НОД( 89; 13)

a и b есть НОД(a, b).
Доказательство
Просмотрим последовательно равенства сверху вниз:
всякий делитель a и b делит r1, r2, . . . , rn.
Если же просматривать эту цепочку равенств от последнего к первому, то видно, что rn|rn−1, rn|rn−2, и так далее, т. е. rn делит a и b.
Поэтому rn — наибольший общий делитель чисел a и b.
Доказательство завершено.

то найдутся такие целые u и v, что
d = a · u + b · v.
Доказательство.
Из цепочки равенств имеем:
rn = rn−2 − rn−1 · qn = rn−2 − (rn−3 − rn−2 · qn-1 ) · qn = . . . (идем по цепочке равенств снизу вверх, выражая из каждого следующего равенства остаток и подставляя его в получившееся уже к этому моменту выражение) . . . = a · u + b · v = НОД(a, b). Доказательство завершено.

число m называется наименьшим общим кратным чисел a и b, если m делится одновременно на a и b и каждое другое общее кратное a и b делится на m.
Обозначается НОК[a, b]. Известно, что НОК двух чисел — единственно

Свойства:

Если НОД(a, b) = 1, то НОК[a, b] = a · b.
a · b = НОД(a, b) · НОК[a, b].

Решение.
НОК — есть натуральное наименьшее число, делящееся на все числа из заданного набора. Так как 8 уже делится на 2, то НОК[2, 5, 8] = 5 · 8 = 40.
Ответ. НОК[2, 5, 8] = 40.

1001 сказку. Сколько ночей потребуется Шехерезаде, чтобы рассказать все свои сказки, если x ночей она будет рассказывать по 3 сказки, а остальные сказки по 5 за у ночей (Сюжет был предложен Б. А. Кордемским в статье «Этому виду задач более 1600 лет» в журнале «Квант» [13]).

b · y = c
с целыми коэффициентами a, b, c, решаемое на множестве целых чисел.

каждый час ему платят 10 р. И высчитывают 2 р. за каждую разбитую тарелку. На прошедшей неделе он заработал 180 р. Определите, сколько часов он работал и сколько разбил тарелок, если известно, что он работает не более 3 ч в день.
Решение.
Пусть x часов он всего работал в неделю, тогда 10х р. ему заплатили, но он разбил у тарелок, и с него вычли 2у р.
Имеем уравнение 10х – 2у =180, причем x меньше или равен 21. Получим: 5х-у=90, 5х=90+у, х=18+у:5.
Так как x целое число, то у должно нацело делится на 5, чтобы в правой части получилось целое число. Возможны четыре случаи:
у=0, х=18, т. е. решением является пара – (18, 0);
у=5, х=19, (19, 5);
у=10, х=20, (20, 10);
у=15, х=21, (21, 15).

среди этих монет двухрублевых?
Решение.
Пусть x – количество двухрублевых монет, у – количество пятирублевых монет. Составим и решим уравнение:
2х+5у=23;
2х=23–5у;
x = (23 – 5у):
2; x =(22+1 – 5у):2, почленно поделим 22 на 2 и (1 – 5у) на 2, получим:
x = 11 + (1 – 5у):2.
Так как x и y натуральные числа по условию задачи, то левая часть уравнения есть натуральное число, значит, и правая часть должна быть натуральным числом. К тому же, чтобы получить в правой части число натуральное, нужно чтобы выражение (1 – 5у) нацело делилось на 2. Осуществим перебор вариантов.
y=1, х=9, то есть двухрублевых монет может быть 9;
у=2, при этом выражение (1 – 5у) не делится нацело на 2;
у=3, х=4, то есть двухрублевых монет может быть 4;
при у больше или равном 4 значение x не является числом натуральным.
Таким образом, ответ в задаче следующий: среди монет 9 или 4 двухрублевых.

x и у – натуральные корни.
Решим это уравнение способом перебора вариантов.
x = (1001 – 5у):3; так как x – натуральное число,
то и в правой части равенства также должно быть натуральное число, а значит выражение (1001 – 5у) должно нацело делиться на 3.
Осуществим перебор вариантов.
у=1, 1001 – 5у=1001-5= 996, 996 делится на 3, следовательно, х=332; решение (332;1);
у=2, 1001– 10=991, 991 не делится на 3;
у=3, 1001 – 15 = 986; 986 не делится на3;
у =4, 1001 – 20 = 981, 981 делится на 3, следовательно, x = 327, решение (327;4) и т. д.

ходе обсуждения задачи можно выполнить несколько переборов вариантов.
Подчеркнуть, что, способ перебора вариантов не совсем эффективен для решения данной задачи, так как для нахождения всех решений уравнения требуются значительные временные затраты.
Все вышесказанное определяет актуальность рассмотрения общих способов решения диофантовых уравнений первой степени.

наибольший общий делитель двух чисел есть последний отличный от нуля остаток в цепочке указанных в примере действий.
Перейдем теперь к решению линейного уравнения с двумя неизвестными:
ax + by = c (1)
Возможны два случая: либо число c делится на d = НОД(a,b), либо нет.
В первом случае можно разделить обе части уравнения на d и свести задачу к решению в целых числах уравнения a1x + b1y = c1, коэффициенты которого a1 = a/d и b1 = b/d взаимно просты.
Во втором случае уравнение не имеет целочисленных решений: при любых целых x и y число ax + by делиться на d и поэтому не может равняться числу c, которое на d не делится.

2. Неопределённые равнения, в котором ищут только целые решения, называются диофантовыми.
Определение3 Неоднородным диофантовым уравнением первого порядка с двумя неизвестными x, y называется уравнение вида
аx + вy = с, где а, в, с, х, у Z с 0
Утверждение 1. Если свободный член с в уравнении (1) не делится на наибольший общий делитель (НОД) чисел а и в, то уравнение (1) не имеет целых решений.
Пример: 34x – 17y = 3. НОД (34; 17) = 17, 3 не делится нацело на 17, в целых числах решения нет.

что а и в станут взаимно простыми.
Утверждение 2. Если а и в уравнения (1) взаимно простые числа, то это уравнение имеет по крайней мере одно решение.
Утверждение 3. Если коэффициенты а и в уравнения (1) являются взаимно простыми числами, то это уравнение имеет бесконечно много решений, найденных из системы:
x = cx0 + bt,
y = cy0 – at.
Здесь t – любое целое число.
(x0 ; y0 ) – какое-либо решение уравнения (1), t Z
Определение4. Однородным диофантовым уравнением первого порядка с двумя неизвестными x, y называется уравнение вида (2)
аx + вy = 0, где а,в, x, y  Z
Утверждение 4. Если а и в – взаимно простые числа, то всякое решение уравнения (2) имеет вид
x = bt,
y = -at.
.

правил, которые можно отобразить в алгоритме
Алгоритм решения линейных диофантовых уравнений
Проверить, имеет ли уравнение решение в целых числах, для этого найти НОД(а,в) с помощью алгоритма Евклида.
Если с делится на НОД(а,в), то уравнение следует упростить разделив обе его части на НОД(а,в).
Найти решения уравнения аx + вy = 1, где а, в, х, у  Z ,выписать их согласно Утверждению 3, а затем умножить их на с.
Вернуться к условиям, накладываемым к решению уравнения.

47x − 111y = 89.
Решение.
Если НОД(a, b) = 1, то найдутся такие x, y, что a · x + b · y = 1.
Тогда выполнится: ax · c + by · c = c.
НОД (47, 111) = 1.
Найдем x, y:
111 = 47 · 2 + 17
47 = 17 · 2 + 13
17 = 13 · 1 + 4
13 = 4 · 3 + 1
4 = =1 · 4 + 0.
Тогда выполняется: 89 = 47 · (89 · 26) − 111 · (89 · 11).
x = 89 · 26 + 111t
y = 89 · 11 - 47t, где t — любое целое.
Ответ. x = 2314 + 111t,
y = 979 - 47t, t = Z.

у0 для получения решений уравнения по формулам (3). Применим алгоритм Евклида к числам 11 и 7:


Таким образом, получаем: , следовательно х0 = –3, у0=2
Запишем общее решение уравнения на множестве целых чисел согласно формулам (3):


Придавая конкретные целые значения t, можно получить частные решения уравнения. Например, при t=1, имеем x= –196, у=131.

11 см и 13 см. Сколько нужно взять досок того и другого размера?
Решение.
Очевидно, что если х - число досок шириной в 11 см, а у – количество досок шириной 13 см, то нам надо решить уравнение
11х+13у=300 в натуральных числах.
Попробуем сначала это уравнение решить в целых числах, а затем уже в натуральных.
НОД(11,13)=1
Находим его линейное разложение: 1=11·6+13·(-5).
Умножаем обе части части на 300, получаем

8x + 14y = 32
1) НОД(8, 14)=2.
2 делится на 32, следовательно, уравнение имеет целые решения и его можно упростить, разделив обе части на 2.
2) Решим уравнение 4x+7y=16.

5

Решение.
1) НОД(9,18)=9.
5 не делится нацело на 9, в целых числах решений нет.
Ответ: нет целых решений.

кассиру в магазине 13 копеек?

Решение.
По условию задачи можно составить cледующее уравнение:
5x+3y=13.
1) НОД(5,3)=1, следовательно, целые решения уравнения имеются.
2) 1=5·(-1)+3·2 – линейное разложение НОД(5,3).
3) 1=5·(-1)+3·2

3x – 4y = 1
14x–46y=72

2. Несколько детей собирали яблоки. Каждый мальчик собрал по 21 кг, а
девочка по 15 кг. Всего они собрали 174 кг. Сколько мальчиков и сколько
девочек собирали яблоки? Ответ: мальчиков 4, девочек 6.

3. В мешке у нищенки Лисы Алисы не менее 250 купюр по 200 рублей и не
менее 100 купюр по 500 рублей Определите число способов, с помощью
которых она может этими купюрами разменять 50000 рублей (только без
обмана!)

4. У вас в кармане монеты достоинством только 7 копеек и 13 копеек, а вам
надо уплатить 43 копейки. Как это сделать?

Алгебра-8, Н.Я. Виленкин, ВО “Наука”, Новосибирск, 1992 г.
3. Конкурсные задачи, основанные на теории чисел. В.Я. Галкин, Д.Ю. Сычугов.
МГУ, ВМК, Москва, 2005г.
4. Задачи повышенной трудности в курсе алгебры 7-9 классов. Н.П. Косрыкина. “Просвещение”, Москва, 1991г.
5. Алгебра 7, Макарычев Ю.Н., “Просвещение”.

диофантовых уравнений более высоких степеней в общем виде отсутствуют. Более того, существуют различные классы диофантовых уравнений, которые не имеют решений. Остановимся подробнее на частных случаях диофантовых уравнений степени > 2.
Пример 11.
а) (2x + y)(5x + 3y) = 7;
б) xy = x + y + 3;
в) x 2 = 14 + y 2 ;
г) x 2 + y 2 = x + y + 2.

идеей перебора. После преобразования уравнения (чаще всего разложение на множители) перебор сводится к ограниченному количеству пар. Например, уравнение xy = x + y + 3 после преобразования имеет вид (x - 1)(y - 1) = 4. Рассматривая разложение 4 в произведение двух целых множителей получаем ответ:
(5; 2), (2; 5), (0;-3),(-3; 0), (3; 3), (-1;-1).