Бинарный алгоритм Евклида
Этот вариант создан специально для реализации на ЭВМ. В нем учитывается, что операция деления на число 2 или на любую степень двойки является весьма быстрой и простой операцией (в двоичной системе счисления операция деления на 2 есть всего лишь битовый сдвиг вправо). Учтем, что (2k∙a,2s∙b)=2min(k,s)(a,b). Алгоритм: Вход: a, b>0. 1. Представим a и b в виде: ; , где a1, b1 – нечетные числа. k:=min(k1,k2). 2. Если a1>b1 Шаг 4 a1< b1 Шаг 3 a1= b1 Шаг 6 3. Меняем местами a1 и b1. 4. c:=a1–b1=2s∙c1 (c1 - нечетное число) (Заметим, что с обязательно будет четным, а значит ) 5. a1:= b1 , b1:=c1 . Возвращаемся на Шаг 1. 6. Выход: (a,b)=2k∙a1 .
Пример a=603, b=108
1. a1=603, k1=0; b=108=4∙27=22∙27 k2=2, b1=27, k=0 2. a1=603> b1=27 Ш4 4. c=603-27=56=64∙9, c1=9 5. a1=27; b1=9 Ш1 1. a1=27; b1=9 2. a1> b1 Ш4 4. c=a1–b1=18=2∙9, c1=9 5. a1=9, b1=9 1. a1=9, b1=9, k=0 2. a1= b1 Ш6 6. (a,b) = 2º∙9=9
Для НОД справедливы следующие свойства:
1) (am,bm)=m(a,b) Доказательство: Доказательство строится, умножая почленно соотношения алгоритма Евклида на m. 2) d – общий делитель чисел a и b (в частности, ). Доказательство: Учитывая, что и – целые числа, из свойства НОД №1 получаем соотношение , что и требовалось. □ 3) (a,b)=1 (ac,b)=(c,b) Доказательство: a, b, c выполняется (ac,b)\ac, (ac,b)\b (ac,b)\bc (ac,b)\(ac,bc). По условию теоремы, в силу взаимной простоты a и b (ac,bc)=c, то есть получили (ac,b)\с. Но (ac,b)\b (ac,b)\(c,b). С другой стороны, (c,b)\ac, (c,b)\b. (c,b)\(ac,b). Таким образом, числа (ac,b) и (c,b). взаимно делят друг друга (ac,b)=(c,b). □ 4) (a,b)=1, b\ac b\c. Доказательство: Из теоремы №1 о НОД в силу b\ac, (ac,b)=b. из свойства НОД № 3 b=(c,b)и тогда из теоремы №1 о НОД b\c. □ 5) Если (ai, bj)=1 для , ( , )=1. Доказательство: имеем ( , ) = ( , ) = ( , ) = … = . Аналогично, используя полученное соотношение, ( , ) = ( , ) = … = ( , ) = 1. □ НОК (наименьшее общее кратное) Если a1\b, a2\b, … , an\b, то b называется общим кратным чисел a1,…,an. Наименьшее положительное общее кратное чисел a1,…,an называется их наименьшим общим кратным (НОК). Пусть НОД(a,b)=d, тогда можно записать a=d∙a1, b=d∙b1, где (a1,b1)=1. Пусть a\M, b\M M=ak для некоторого целого k, и тогда число – целое. Но, поскольку (a1,b1)=1, то b1\k , и тогда k=b1t для некоторого , и . * Очевидно, , М – общее кратное a и b, и (*) дает формулу всех общих кратных. При t=1 имеем M=НОК(a,b). Формулой M = НОК(a,b)∙t можно представить все общие кратные чисел a и b. ( ).
Простые числа Числа a1,…,an называются взаимно простыми, если НОД(a1,…,an)=1, попарно простыми, если , НОД(ai,aj)=1. Если числа попарно a1,…,an простые, то они взаимно простые. Обратное неверно. Число p называется простым, если оно имеет лишь два делителя – “1” и р. Число “1” делится только на себя, и не является ни простым, ни составным, а занимает особое место в теории чисел. Число а>1 имеющее более двух делителей, называется составным. Утверждение 1 Наименьший не равный единице делитель числа a: , >1, является простым числом. Доказательство: □ Утверждение 2 p – наименьший делитель составного числа а, p≠1 . Доказательство: Представим a в виде a=pa1. Поскольку p – наименьший делитель числа a, то a1≥p a≥p2 в силу монотонности квадратичной функции на положительной полуоси, p≤ . □
Популярное: Почему люди поддаются рекламе?: Только не надо искать ответы в качестве или количестве рекламы... Как вы ведете себя при стрессе?: Вы можете самостоятельно управлять стрессом! Каждый из нас имеет право и возможность уменьшить его воздействие на нас... Почему человек чувствует себя несчастным?: Для начала определим, что такое несчастье. Несчастьем мы будем считать психологическое состояние... Почему двоичная система счисления так распространена?: Каждая цифра должна быть как-то представлена на физическом носителе... ©2015-2024 megaobuchalka.ru Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. (679)
|
Почему 1285321 студент выбрали МегаОбучалку... Система поиска информации Мобильная версия сайта Удобная навигация Нет шокирующей рекламы |