Нод и нок многочленов реферат

Обновлено: 05.07.2024

$ \mathbb, \mathbb[X], A[X]$ над целостным кольцом $A$.

Обратимые элементы – регулярные.

$ f \in \mathbb$ – обратим $\Rightarrow \deg=0$

$a$ делится на $b$, если $a=bc ~~ b|a$

$a|b$ и $b|a \Rightarrow a,b$ – ассоциированы.

$p$ – простой, если $p$ нельзя представить в виде $p=ab$, где $a,b$ – необратимые.

Простой элемент $\mathbb[X]$ – неприводимый многочлен.

Свойства делимости

1) $a|b, b|c \Rightarrow a|c$

2) $c|a, c|b \Rightarrow c|(a \pm b)$

3) $a|b \Rightarrow a|bc$

4) $b_1. b_m$ делится на $a \Rightarrow b_1c_1+. +b_mc_m$ делится на $a$

Определение. $K$ – факториальное кольцо, если любой элемент $a \in K$ можно представить в виде
$a=up_1. p_k~ (u$ – обратим, $p_i$ – простой) единственным образом.

$a=vq_1. q_m \Rightarrow m=k ~~ (q_i=u_ip_i, u_i$ – обратимый элемент).

Теорема. Пусть $K$ – произвольное целостное кольцо с разложением на множители. Тогда факториальность $K$
эквивалентна утверждению: любой $p$ – простой, делящий $ab$, делит по крайней мере один из множителей.

НОД и НОК в кольцах

2) $c|a$ и $c|b \Rightarrow c|d$

НОД$(a,b)$ определен с точностью до ассоциированных элементов.

$a,b$ – ассоциированные, если $a=ub, u$ – обратимый.

Свойства

1) НОД$(a,b)=a \Rightarrow a|b$

4) НОД(НОД$(a,b),c)$ = НОД$(a,$ НОД$(b,c))$

2) $a|c$ и $b|c \Rightarrow m|c$

Теорема

а) НОК$(a,b)=0 \Rightarrow a=0$ или $b=0$

б) $ab \neq 0, ~~m=$ НОК$(a,b), ~~ab=dm \Rightarrow d=$ НОД$(a,b)$

Признак делимости

$a,b$ – элементы факториального кольца.

1) $a|b \Leftrightarrow k_i \leqslant l_i$

Факториальность евклидовых колец

$K$ – целостное кольцо.

$\delta: K \setminus \ \rightarrow \mathbb \cup \$

E1) $\delta(ab) \geqslant \delta(a)$ для любых $a,b \in K \setminus \$

E2) каковы бы ни были $a,b~(b \neq 0)$, найдутся такие $q,r$:

$a=qb+r,~\delta(r) \delta(a_1. a_) > \delta(a_1. a_) > . > \delta(a_1) > \delta(1)$

$m \leqslant \delta(a)$

Разложение с максимальным количеством множителей – разложение $a.~\blacksquare$

Теорема. Всякое евклидово кольцо факториально.

$\blacktriangle~ p$ – простой элемент кольца $K$

$p|bc \Rightarrow p|b$ или $p|c$

$b=0$ или $c=0$ – очевидно.

$d=p \Rightarrow p|b$

$d=1 \Rightarrow (a|bc,$ НОД$(a,b)=1 \Rightarrow a|c)$

Следствие. Кольца $\mathbb$ и $\mathbb[X]$ факториальны.

$\mathbb[x_1. x_n]$ – неевклидово, тем не менее $\mathbb[x_1. x_n]$ – факториально.

Неприводимые многочлены

Неприводимые многочлены – простые элементы в $\mathbb[X]$

Над любым конечным полем существуют неприводимые многочлены сколь угодно высокой степени.

$f$ – неприводимый многочлен над $\mathbb[X] \Rightarrow f$ – неприводимый многочлен над $\mathbb[X]$

Критерий неприводимости Эйзенштейна

$a_1. a_n$ делятся на простое $p$, при этом $a_n$ не делится на $p^2 \Rightarrow f$ – неприводим над $\mathbb$.

$\blacktriangle~ f$ – приводим $\Rightarrow f=(x^s+b_1x^+. +b_s)(x^t+. +c_t)$ над $\mathbb_p,~f \in \mathbb_p[X]=x^n$

$b_s$ делится на $p,~c_t$ делится на $p$.

$a_n=b_sc_t \Rightarrow a_n$ делится на $p^2$ – противоречие. $\blacksquare$

НАХОЖДЕНИЕ И ПРИМЕНЕНИЕ НОД И НОК

Автор работы награжден дипломом победителя III степени

Текст работы размещён без изображений и формул.
Полная версия работы доступна во вкладке "Файлы работы" в формате PDF

Введение.

В каждодневной жизни человеку приходится решать большое число разного рода задач, которые требуют применения определённых алгоритмов. Когда мы приготавливаем чай, пользуемся определённым алгоритмом (иногда заданным инструкцией, напечатанной на упаковке).

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

Данная работа знакомит с алгоритмами вычисления НОД и НОК. Знакомство с ними не только дополняет и углубляет математические знания, но и развивает интерес к предмету, любознательность и логическое мышление. Предлагаемая работа рассчитана на учеников, желающих повысить уровень математической подготовки, увидеть красоту математических выкладок и эстетику алгоритма Евклида.

Гипотеза:Есть алгоритмы нахождения НОД и НОК, которые являются удобными и не требующие громоздкого способа вычисления.

Цель исследования: изучить разные алгоритмы вычисления НОД и НОК, выявить наиболее рациональные способы решения, красиво и сравнительно просто приводящие к ответу.

Достижение поставленной цели требует решения следующих основных задач:

Рассмотреть несколько алгоритмов вычисления НОД и НОК

Сравнить алгоритмы для вычисления НОД и НОК

Предмет исследования: Алгоритмы вычисления НОД и НОК

Объект исследования: умения и навыки вычисления НОД и НОК

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

Для данного алгоритма существует множество теоретических и практических применений. В частности он широко распространён в электронной коммерции. Также алгоритм используется при решении диофантовых уравнений (Уравнения в целых числах – это алгебраические уравнения с двумя или более неизвестными переменными и целыми коэффициентами). Решениями такого уравнения являются все целочисленные (иногда натуральные или рациональные) наборы значений неизвестных переменных, удовлетворяющих этому уравнению. Такие уравнения ещё называют диофантовыми, в честь древнегреческого математика Диофанта Александрийского, например: Решить в целых числах уравнение x 2 – xy – 2y 2 = 7), при построении непрерывных дробей. Алгоритм Евклида является основным инструментом для доказательства теорем в современной теории чисел. [2.3]

Долгое время алгоритм Евклида был самым эффективным способом отыскания наибольшего общего делителя, однако с появлением электронно-вычислительных машин ситуация изменилась Учет специфических особенностей выполнения арифметических операций компьютером позволил построить более эффективную (для программной реализации) версию алгоритма Евклида.

1. 2. Алгоритмы вычисления НОД 1.2.1 Алгоритм простого перебора

Чтобы найти наибольший общий делитель двух данных натуральных чисел можно действовать по определению: выписать все делители этих чисел, выделить среди них общие и выбрать среди всех общих делителей наибольший.

Пример. Найдем все делители чисел 54 и 36.

54 делится на 1; 2; 3; 6; 9; 18; 27; 54.

36 делится на 1; 2; 3; 4; 6; 9; 18; 36.

Общими делителями являются числа: 1, 2, 3, 6, 9, 18.

Значит НОД(54; 36)=18

1.2.2 Нахождение НОД с помощью разложения чисел на простые множители

Рассмотрим еще один способ нахождения НОД. Наибольший общий делитель может быть найден по разложениям чисел на простые множители.

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

Смысл разложения на множители предельно прост и понятен. Прямо из самого названия. Например, надо разложить число 12. Можно смело записать: 12=3·4

А можно разложить 12 по-другому: 12=3·4=2·6=3·2·2=0,5·24=.

Вариантов разложения - бесконечное количество.

Сформулируем правило: НОД двух целых положительных чисел a и b равен произведению всех общих простых множителей, находящихся в разложениях чисел a и b на простые множители.

Приведем пример для пояснения правила нахождения НОД.

Пусть нам известны разложения чисел 220 и 600 на простые множители, они имеют вид 220=2·2·5·11 и 600=2·2·2·3·5·5. Общими простыми множителями, участвующими в разложении чисел 220 и 600, являются 2, 2 и 5. Следовательно, НОД(220, 600)=2·2·5=20.

Таким образом, если разложить числа a и b на простые множители и найти произведение всех их общих множителей, то будет найден наибольший общий делитель чисел a и b.

Пример. Найдите наибольший общий делитель чисел 72 и 96.

Решение. Разложим числа 72 и 96 на простые множители.

72=2·2·2·3·3 и 96=2·2·2·2·2·3. Общими простыми множителями являются 2, 2, 2 и 3. Таким образом, НОД(72, 96)=2·2·2·3=24.

Ответ: НОД(72, 96)=24.

В заключение этого пункта заметим, что справедливость приведенного правила нахождения НОД следует из свойства наибольшего общего делителя, которое утверждает, что

НОД(m·a, m·b)=m·НОД(a, b), где m – любое целое положительное число.

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

Одним из простейших алгоритмов нахождения наибольшего общего делителя является Алгоритм Евклида. Он может быть реализован, как при помощи вычитания, так и деления. Рассмотрим каждый из этих двух способов.

а) Описание алгоритма нахождения НОД вычитанием:

Из большего числа вычитаем меньшее. Если получается 0, то значит, что числа равны друг другу и являются НОД (следует выйти из цикла). Если результат вычитания не равен 0, то большее число заменяем на результат вычитания.

Переходим к пункту 1.

Найти НОД для 30 и 18.

6 – 6 = 0 Конец: НОД – это уменьшаемое или вычитаемое. НОД (30, 18) = 6

б) Описание алгоритма нахождения НОД делением:

Большее число делим на меньшее. Если делится без остатка, то меньшее число и есть НОД (следует выйти из цикла). Если есть остаток, то большее число заменяем на остаток от деления. Переходим к пункту 1.

Пусть требуется найти НОД(102;84). Разделим одно число на другое и определим остаток.

Достижение поставленной цели требует решения следующих основных задач:

Муниципальное бюджетное общеобразовательное учреждение

"Многопрофильный лицей" городского поселения "Рабочий поселок Чегдомын" Верхнебуреинского муниципального

района Хабаровского края.

Реферативно-исследовательская работа по математике:

Тема: "Нахождение и применение НОК и НОД"

Выполнила: Крюкова Екатерина

ученица 6"А" класса

Руководитель: Терентьева О. А.

1.Введение 3 2.История возникновения алгоритмов вычисления НОД и НОК 4

метода математической индукции

3.Основные результаты исследования 5-10

4.Заключение 11 5.Список литературы 12

Достижение поставленной цели требует решения следующих основных задач:

Рассмотреть несколько алгоритмов вычисления НОД и НОК

История возникновения алгоритмов вычисления НОД и НОК

Для данного алгоритма существует множество теоретических и практических применений. В частности, он широко распространён в электронной коммерции. Также алгоритм используется при решении диофантовых уравнений. Алгоритм Евклида является основным инструментом для доказательства теорем в современной теории чисел.

Основные результаты исследования

Давайте рассмотрим все алгоритмы нахождения НОД.

Алгоритм простого перебора: Чтобы найти наибольший общий делитель двух данных натуральных чисел можно действовать по определению: выписать все делители этих чисел, выделить среди них общие и выбрать среди всех общих делителей наибольший.

Пример. Найдем все делители чисел 54 и 36.

54 делится на 1; 2; 3; 6; 9; 18; 27; 54.

36 делится на 1; 2; 3; 4; 6; 9; 18; 36.

Общими делителями являются числа: 1, 2, 3, 6, 9, 18.

Наибольший из них является 18.

Значит НОД (54; 36) = 18

Нахождение НОД с помощью разложения чисел на простые множители:

Что такое разложение на множители? Это способ превращения неудобного и сложного примера в простой. Встречается на каждом шагу и в элементарной, и в высшей математике.

А можно разложить 12 по-другому: 12=3·4=2·6=3·2·2=.

Приведем пример для пояснения правила нахождения НОД.

Пример. Найдите наибольший общий делитель чисел 72 и 96.

Решение. Разложим числа 72 и 96 на простые множители.

72=2·2·2·3·3 и 96=2·2·2·2·2·3. Общими простыми множителями являются 2, 2, 2 и 3. Таким образом, НОД (72, 96) = 2·2·2·3=24.

Ответ: НОД (72, 96) = 24.

НОД (m ·a, m ·b) = m· НОД (a, b), где m – любое целое положительное число.

Описание алгоритма нахождения НОД вычитанием:

Из большего числа вычитаем меньшее. Если получается 0, то значит, что числа равны друг другу и являются НОД. Если результат вычитания не равен 0, то большее число заменяем на результат вычитания.

Пример:

Найти НОД 30 и 18.

НОД – это уменьшаемое или вычитаемое. НОД (30, 18) = 6

Описание алгоритма нахождения НОД делением:

Пример:

Пусть требуется найти НОД(30;18). Разделим одно число на другое и определим остаток.

30 / 18 = 1 (остаток 12)
18 / 12 = 1 (остаток 6)
12 / 6 = 2 (остаток 0)
НОД – это делитель 6.
НОД (30, 18) = 6

Способов нахождения НОД очень много, мы рассмотрели самые известные.

Теперь давайте рассмотрим несколько способов нахождения НОК.

Наименьшее общее кратное-это наименьшее число, которое делится на все заданные числа.

Способ перемножения чисел: Он гораздо лучше подходит для простых однозначных или двухзначных чисел. Большие числа принято разделять на множители, чем больше число, тем больше множителей будет.

Найти НОК можно, по очереди, для каждого из заданных чисел, выписывая в порядке возрастания все числа, которые получаются путем их умножения на 1, 2, 3, 4 и так далее.

Найдем НОК (6; 9)
Умножаем число 6, последовательно, на 1, 2, 3, 4, 5.
Получаем: 6, 12, 18, 24, 30
Умножаем число 9, последовательно, на 1, 2, 3, 4, 5.
Получаем: 9, 18, 27, 36, 45
Общее кратное у них =18 ,следовательно НОК(6;9)=18

Наименьшее общее кратное через НОД.

НОК (а; b) = a*b:НОД (a, b)

Рассмотрим примеры нахождения НОК по приведенной формуле:

Сначала нам предстоит найти наибольший общий делитель, после чего мы должны вычислить НОК.

Найдем НОД(126;70), используя алгоритм Евклида:

56=14х4, следовательно, НОД(126;70) =14

Теперь находим требуемое наименьшее общее кратное:

НОК(126;70) =126х70: НОД (126;70126х70:14=630

Способов нахождения НОК не много, мы рассмотрели самые известные.

Памятка. НОД и НОК

Признаки делимости натуральных чисел.

Признак делимости на 2

Если запись натурального числа оканчивается четной цифрой, то это число делится без остатка на 2, а если запись числа оканчивается нечетной цифрой, то это число не делится без остатка на 2.

Например, числа 60, 308, 84 делятся без остатка на 2, а числа 51, 85, 167 не делятся без остатка на 2.

Признак делимости на 3

Если сумма цифр числа делится на 3, то и число делится на 3; если сумма цифр числа не делится на 3, то и число не делится на 3.

Признак делимости на 5

Если запись натурального числа оканчивается цифрой 0 или 5, то это число делится без остатка на 5. Если же запись числа оканчивается иной цифрой, то число без остатка на 5 не делится.

Например, числа 15, 30, 1765, 475300 делятся без остатка на 5, а числа 17, 378, 91 не делятся.

Признак делимости на 9

Если сумма цифр числа делится на 9, то и число делится на 9; если сумма цифр числа не делится на 9, то и число не делится на 9.

Признак делимости на 10

Если запись натурального числа оканчивается цифрой 0, то это число делится без остатка на 10. Если запись натурального числа оканчивается другой цифрой, то оно не делится без остатка на 10.

Например, числа 40, 170, 14090 делятся без остатка на 10, а числа 17, 93, 14307 — не делятся.

В своей работе я попыталась показать эффективность использования различных алгоритмов вычисления НОД и НОК чисел, из которых каждый ученик может выбрать те, которые показались ему целесообразными, и применять их на практике.

Научиться быстро и правильно вычислять НОК и НОД чисел не так уж сложно. Вышеперечисленные алгоритмы рассчитаны на ум "обычного" человека и не требуют уникальных способностей. Главное - более или менее продолжительная тренировка.

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

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

ГОСТ

Наибольший общий делитель

Наибольшее натуральное число, на которое делятся без остатка числа $a$ и $b$, называется наибольшим общим делителем и часто обозначается НОД.

Если натуральное число a делится на натуральное число $b$, то $b$ называют делителем числа $a$, а число $a$ называют кратным числа $b$.

Пусть $a$ и $b$-натуральные числа. Число $c$ называют общим делителем и для $a$ и для $b$.

Множество общих делителей чисел $a$ и $b$ конечно, так как ни один из этих делителей не может быть больше, чем $a$. Значит ,среди этих делителей есть наибольший, который называют наибольшим общим делителем чисел $a$ и $b$ и для его обозначения используют записи :

$НОД \ (a;b) \ или \ D \ (a;b)$

Чтобы найти наибольший общий делитель двух, чисел необходимо:

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

Найти НОД чисел $121$ и $132.$

Будем находить согласно представленному алгоритму. Для этого

разложить числа на простые множители

$242=2\cdot 11\cdot 11$

$132=2\cdot 2\cdot 3\cdot 11$

Выбрать числа, которые входят в разложение этих чисел

$242=2\cdot 11\cdot 11$

$132=2\cdot 2\cdot 3\cdot 11$

Найти произведение чисел , найденных на шаге 2.Полученное число и будет искомым наибольшим общим делителем.

Найти НОД одночленов $63$ и $81$.

Будем находить согласно представленному алгоритму. Для этого:

Разложим числа на простые множители

$63=3\cdot 3\cdot 7$

$81=3\cdot 3\cdot 3\cdot 3$

Выбираем числа, которые входят в разложение этих чисел

$63=3\cdot 3\cdot 7$

$81=3\cdot 3\cdot 3\cdot 3$

Найдем произведение чисел , найденных на шаге 2.Полученное число и будет искомым наибольшим общим делителем.

Готовые работы на аналогичную тему

Найти НОД двух чисел можно и по-другому, используя множество делителей чисел.

Найти НОД чисел $48$ и $60$.

Решение:

Найдем множество делителей числа $48$: $\left\\right\>$

Теперь найдем множество делителей числа $60$:$\ \left\\right\>$

Найдем пересечение этих множеств: $\left\\right\>$- данное множество будет определять множество общих делителей чисел $48$ и $60$. Наибольший элемент в данном множестве будет число $12$. Значит наибольший общий делитель чисел $48$ и $60$ будет $12$.

Определение НОК

Общим кратным натуральных чисел $a$ и $b$ называется натуральное число, которое кратно и $a$ и $b$.

Общими кратными чисел называются числа которые делятся на исходные без остатка.Например для чисел $25$ и $50$ общими кратными будут числа $50,100,150,200$ и т.д

Наименьшее из общих кратных будет называться наименьшим общим кратным и обозначается НОК$(a;b)$ или K$(a;b).$

Чтобы найти НОК двух чисел, необходимо:

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

Найти НОК чисел $99$ и $77$.

Будем находить согласно представленному алгоритму. Для этого

Разложить числа на простые множители

$99=3\cdot 3\cdot 11$

Выписать множители, входящие в состав первого

добавить к ним множители, которые входят в состав второго и не ходят в состав первого

Найти произведение чисел , найденных на шаге 2.Полученное число и будет искомым наименьшим общим кратным

$НОК=3\cdot 3\cdot 11\cdot 7=693$

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

Утверждения, на которых основан алгоритм Евклида:

Если $a$ и $b$ --натуральные числа, причем $a\vdots b$, то $D(a;b)=b$

Если $a$ и $b$ --натуральные числа, такие что $b

Пользуясь $D(a;b)= D(a-b;b)$, можно последовательно уменьшать рассматриваемые числа до тех пор, пока не дойдем до такой пары чисел, что одно из них делится на другое. Тогда меньшее из этих чисел и будет искомым наибольшим общим делителем для чисел $a$ и $b$.

Свойства НОД и НОК

Любое общее кратное чисел $a$ и $b$ делится на K$(a;b)$
Если $a\vdots b$ , то К$(a;b)=a$

Если К$(a;b)=k$ и $m$-натуральное число, то К$(am;bm)=km$

Если $a\vdots c$ и $b\vdots c$ ,то $\frac$ - общее кратное чисел $a$ и $b$

Читайте также: