Как найти квадратный корень по методу евклида. Математика, которая мне нравится

Размер: px

Начинать показ со страницы:

Транскрипт

1 ЛЕКЦИЯ 2 ВЫЧИСЛЕНИЕ НАИБОЛЬШЕГО ОБЩЕГО ДЕЛИТЕЛЯ Алгоритм Евклида При работе с большими составными числами их разложение на простые множители, как правило, неизвестно. Но для многих прикладных задач теории чисел поиск разложения числа на множители является важной, часто встречающейся практической задачей. В теории чисел существует сравнительно быстрый способ вычисления НОД двух чисел, который называется алгоритмом Евклида. Алгоритм 1. Алгоритм Евклида . Вход. Целые числа а, b; 0 < b < а. Выход. d = НОД (a,b). 1. Положить r 0 a, r 1 b, i Найти остаток r i+1 от деления r i 1 на r i. 3. Если r i+1 = 0, то положить d r i. В противном случае положить i i + 1 и вернуться на шаг Результат: d. Теорема. Для любых а, b > 0 алгоритм Евклида останавливается и выдаваемое им число d является наибольшим общим делителем чисел а и b. Доказательство . По теореме о делении с остатком для любого i 1 имеем r i 1 = q i r i + r i+1, где 0 r i+1 < r i. Получаем монотонно убывающую последовательность неотрицательных целых чисел r 1 > r 2 > r 3 >... 0, ограниченную снизу. Такая последовательность не может быть бесконечной, следовательно, алгоритм Евклида останавливается. Бинарный алгоритм Евклида Бинарный алгоритм Евклида вычисления НОД оказывается более быстрым при реализации этого

2 алгоритма на компьютере, поскольку использует двоичное представление чисел а и b. Бинарный алгоритм Евклида основан на следующих свойствах наибольшего общего делителя (считаем, что 0 < b а): 1) если оба числа а и b четные, то НОД(a,b) = 2 НОД(a/2, b/2) 2) если число а нечетное, число b четное, то НОД(a, b) = НОД(а, b/2); 3) если оба числа а и b нечетные, а > b, то НОД(а, b) = НОД(а b, b); 4) если а = b, то НОД(а, b) = а. Алгоритм 2. Бинарный алгоритм Евклида . Вход. Целые числа a, b; 0 < b а. Выход. d = HOД(a,b). 1. Положить g Пока оба числа а и b четные, выполнять а a/2, b b/2, g 2g до получения хотя бы одного нечетного значения а или b. 3. Положить u a, v b. 4. Пока u 0, выполнять следующие действия Пока u четное, полагать u u/ Пока v четное, полагать v v/ При u v положить u u v. В противном случае положить v v u. 5. Положить d gv. 6. Результат: d. Расширенный алгоритм Евклида Расширенный алгоритм Евклида находит наибольший общий делитель d чисел а и b и его линейное представление, т. е. целые числа x и у, для которых ах + by = d, и не требует «возврата», как в рассмотренном примере. Пусть d НОД для a и b, т. е. d = (a, b), где a > b. Тогда существуют такие целые числа x и y, что d = ax + by. Иными словам, НОД двух чисел можно представить в

3 виде линейной комбинации этих чисел с целыми коэффициентами. Алгоритм 3. Схема расширенного алгоритма Евклида. 1. Определить = 1, = 0, = 0, = 1, α = a, β = b. 2. Пусть число q частное от деления числа a на число b, а число r остаток от деления этих чисел (т. е. a = qb + r). a = b; b = r; t = ; //t = x i-1 ; = t q; // = x i для правой части = x i+1 для правой; //t = y i-1 ; = t q; 5. Возвращаемся на шаг Определяем x = x 0, y = y 0, d = αx + βy. Вариант расширенного алгоритма Евклида Вход. Целые числа а, b; 0 < b а. Выход: d = НОД(а, b); такие целые числа х, у, что ах + by = d. 1. Положить r 0 а, r 1 b, х 0 1, x 1 0, у 0 0, y 1 1, i 1 2. Разделить с остатком r i 1 на r i,: r i 1 = q i r i +r i Если r i+1 = 0, то положить d r i, х x i у y i. В противном случае положить x i+1 x i 1 x i, y i+1 y i 1 y i, i i + 1 и вернуться на шаг Результат: d, х, у. Корректность определения чисел х и у,

4 вычисляемых алгоритмом, показывает следующая теорема. Теорема 4. На каждой итерации алгоритма 3 выполняется равенство аx i + by i = r i, при i 0. Доказательство . Воспользуемся методом математической индукции. Для i = 0 и i = 1 требуемое равенство имеет место в силу шага 1 алгоритма 3. Допустим, что оно справедливо для i 1 и для i. Тогда на шаге 3 получаем x i+1 = x i 1 x i и y i+1 = y i 1 y i. Следовательно, аx i+1 + by i+1 = a(x i 1 x i) + b(y i 1 y i,) = ax i 1 + by i 1 (ax i + by i) = r i 1 r i = r i+1. Пример. Дано a = 1769, b = 551. Используя расширенный алгоритм Эвклида, найти целые числа x и y такие, что d = ax + by, где d НОД чисел a и b. I этап последовательности вычислений. 1. Определить = 1, = 0, = 0, = 1, α = 1769, β = Частное от деления q = a/b = 1769/551 = 3, а остаток от деления r = 116. a = 551; b = 116; t = =0: = t q = 1 0 = 1 = 0; = t q = 3; следующие промежуточные значения

5 параметров: a= 551, b = 116, = 0, = 1, = 1, = Так как остаток от деления r 0, то возвращаемся на шаг 2. II этап последовательности вычислений. 1. Значение параметров: a = 551, b = 116, = 0, = 1, = 1, = Частное от деления q = a/b = 551/116 = 4, а остаток от деления r = 87. a = 116; b = 87; t = = 0; =1: = t q = = 4 = 3; = t q = 1 (3) 4 = 13; следующие промежуточные значения параметров: a= 116, b = 87, = 1, = 4, = 3, = Так как остаток от деления r 0, то возвращаемся на шаг 2. III этап последовательности вычислений. 1. Значение параметров: a= 116, b = 87, = 1, = 4, = 3, = Частное от деления q = a/b = 116/87 = 1, а остаток от деления r = 29.

6 a = 87; b = 29; t = = 4: = t q = 1 (4) 1 = 5; = 3; = 13; = t q = 3 (13) 1 = 16; следующие промежуточные значения параметров: a= 87, b = 29, = 4, = 5, = 13, = Так как остаток от деления r 0, то возвращаемся на шаг 2. IV этап последовательности вычислений. 1. Значение параметров: a= 87, b = 29, = 4, = 5, = 13, = Частное от деления q = a/b = 87/29 = 3, а остаток от деления r = 0. a = 87; b = 29; t = = 4; = 5; = 19; = 13; = 16; = t q = 13 (16) 3 = 61; следующие промежуточные значения параметров: a= 87, b = 29, = 5, = 19, = 16, = Так как остаток от деления r = 0, то выполняем шаг 6.

7 6. Вычисляем НОД по формуле d = αx + βy, где x = x 0 = 5, y = y 0 = 16, α= 1769, β = 551. Подставляя значение параметров, получаем d = αx + βy = = = 29. Расширенный алгоритм Евклида можно реализовать и в двоичном виде. Алгоритм 4. Расширенный бинарный алгоритм Евклида . Вход. Целые числа а, b; 0 < b а. Выход. d = НОД(a, b); такие целые числа х, у, что ах + by = d. 1. Положить g Пока оба числа а и b четные, выполнять а a/2, b b/2, g 2g до получения хотя бы одного нечетного значения а или b. 3. Положить u a, v b, А 1, В 0, С 0, D Пока u 0, выполнять следующие действия Пока u четное, положить u u/ Если оба числа А и B четные, то положить A A/2, B B/2. В противном случае положить A (A+b)/2, B (B a)/ Пока v четное: Положить v v/ Если оба числа С и D четные, то положить С C/2, D D/2. В противном случае положить C (C + b)/2, D (D a)/ При u v положить u u v, А А С, В В D. В противном случае положить v v u, C C A, D D B. 5. Положить d gv, x С, у D. 6. Результат: d, х, у.

Решение уравнений в целых числах Линейные уравнения. Метод прямого перебора Пример. В клетке сидят кролики и фазаны. Всего у них 8 ног. Узнать сколько в клетке тех и других. Укажите все решения. Решение.

Занятие 7 Число d называется наибольшим общим делителем (НОД) чисел a и b, если (1) d a и d b, а также (2) для всех x из x a и x b следует x d. В этом случае пишем d = (a, b). Лемма 1. Для любых чисел

Тема. Основы элементарной теории чисел и приложения- Теоретический материал. Множество вычетов по модулю, свойства сравнений. Пусть натуральное число, большее. Через Z обозначаем множество всех классов

Югорский физико-математический лицей ВП Чуваков ОСНОВЫ ТЕОРИИ ЧИСЕЛ Конспект лекций (0)(mod) (0)(mod) Натуральные числа N, - множество натуральных чисел, используемых для счета или перечисления

Глава 2 Целые, рациональные и вещественные числа 2.. Целые числа Числа, 2, 3,... называются натуральными. Множество всех натуральных чисел обозначается N, т.е. N = {,2,3,...}. Числа..., 3, 2,0,2,3,...

Цепные дроби Конечные цепные дроби Определение Выражение вида a 0 + a + a + + a m где a 0 Z a a m N a m N/{} называется цепной дробью а m - длиной цепной дроби a 0 a a m будем называть коэффициентами цепной

ЛЕКЦИЯ 1 НЕКОТОРЫЕ ЭЛЕМЕНТЫ ТЕОРИИ ЧИСЕЛ В пособии не излагается теория чисел а дан минимальный инструментарий из этой теории который в дальнейшем потребуется для изучения криптографических систем используемых

Горбачев НЕ Многочлены от одной переменной Решение уравнений степени Понятие многочлена Арифметические операции над многочленами Опр Многочленом (полиномом) -й степени относительно переменной величины

Делимость целых чисел Число а делится на число b (или b делит а) если существует такое число с, что а=bc При этом число c называется частным от деления а на b Обозначения: a - а делится на b или ba b делит

ЛЕКЦИЯ 12 СРВНЕНИЯ ВТОРОЙ СТЕПЕНИ ПО ПРОСТОМУ МОДУЛЮ И КВАДРАТИЧНЫЕ ВЫЧЕТЫ Общий вид сравнения второй степени по простому модулю р имеет вид (1) с 0 х 2 + с 1 х + с 2 0 mod p. Поиск решения сравнения (1)

Указания, решения, ответы УРАВНЕНИЯ В ЦЕЛЫХ ЧИСЛАХ. Уравнение с одной неизвестной.. Решение. Подставим в уравнение. Получим равенство (4a b 4) (a b 8) 0. Равенство A B 0, где А и В целые, выполняется,

Алгебраические многочлены. 1 Алгебраические многочлены степени n над полем K Определение 1.1 Многочленом степени n, n N {0}, от переменной z над числовым полем K называется выражение вида: fz = a n z n

Лекция Квадратичные вычеты и невычеты Лектор: НЮ Золотых Записал: Е Замараева?? сентября 00 Содержание Квадратичные вычеты и невычеты Символ Лежандра Свойства символа Лежандра Квадратичный закон взаимности

ГОУ Школа-интернат ""Интеллектуал"" И с с л е д о в а т е л ь с к а я р а б о т а п о м а т е м а т и к е на тему: «О представимости натуральных чисел в виде линейной комбинации с целыми коэффициентами»

Математический анализ Раздел: Неопределенный интеграл Тема: Интегрирование рациональных дробей Лектор Пахомова Е.Г. 0 г. 5. Интегрирование рациональных дробей ОПРЕДЕЛЕНИЕ. Рациональной дробью называется

4 Теория чисел 4 Целые числа 7 Определение Пусть, b Z Тогда делит b, если существует целое число такое что b (обозначается b) 73 Теорема (деление с остатком) Если, b Z и b, тогда найдутся такие целые

Математический анализ Раздел: Неопределенный интеграл Тема: Интегрирование рациональных дробей Лектор Рожкова С.В. 0 г. 5. Интегрирование рациональных дробей ОПРЕДЕЛЕНИЕ. Рациональной дробью называется

009-00 уч. год. 6, 9 кл. Математика. Элементы теории чисел. 4. Вычисление наибольшего общего делителя и наименьшего общего кратного Сохраним обозначения из параграфа. Для натурального числа n запись n

ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля (поля Галуа). I 1 / 67 Часть I Конечные поля (поля Галуа). I ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля (поля Галуа). I 2 / 67 Поля вычетов по модулю простого

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

Лабораторная работа 8 Вычисление наибольшего общего делителя для двух чисел при помощи алгоритма Евклида Цель работы используя алгоритм Эвклида создать программу, которая для чисел a и b определяет наибольший

Раздел 1. Математические основы криптографии 1 Определение поля Конечным полем GF q (или полем Галуа) называют конечное произвольное множество элементов с заданными между ними операциями сложения, умножения

XIX Межрегиональная олимпиада школьников по математике и криптографии Задачи для 11 класса Решение задачи 1 Сначала заметим, что если N = pq, где p и q простые числа, то количество натуральных чисел, меньших

Многочлены и их корни 2018 г. Гущина Елена Николаевна Определение: Многочленом степени n n N называется всякое выражение вида: P & z = a & z & + a &+, z &+, + + a, z + a., где a &, a &+, a, a. R, a &

Лекция 4. СТАНДАРТ AES. АЛГОРИТМ RIJNDAEL. Стандарт AES (Advnced Encrypton Stndrd) представляет собой новый стандарт шифрования с одним ключом, который заменил стандарт DES. Алгоритм Rjndel (рейн-дал)

Многочлены и их корни Определение: Многочленом степени n (n N) называется всякое выражение вида: P n (z) = a n z n + a n 1 z n 1 + + a 1 z + a 0, где a n, a n 1, a 1, a 0 R, a n старший коэффициент, a

1 Алгоритм Евклида и его сложность Определение 1. Общим делителем чисел a и b называется такое число c, что c a и c b. Определение 2. Наибольшим общим делителем чисел a и b называется такой их общий делитель,

ЛЕКЦИЯ 14 Вычисление квадратных корней по составному модулю Из приведенной выше теории следует, что если =, где и простые числа, группа Z изоморфна пространству Z Z. Поскольку изоморфизм сохраняет свойства

ЛЕКЦИЯ 3 ВЫЧИСЛЕНИЕ КВАДРАТНЫХ КОРНЕЙ ПО МОДУЛЮ Случай простого модуля Рассмотрим сравнение х a mod р, () где число р простое и целое число а не делится на p Вычисление решения x данного уравнения является

Программа коллоквиума по дискретной математике (основной поток) В начале коллоквиума Вы получите билет, в котором будет три вопроса: вопрос на знание определений, задача, вопрос на знание доказательств.

Алгоритм Шора Ю. Лифшиц. 1 декабря 005 г. План лекции 1. Подготовка (a) Разложение чисел на множители (b) Квантовые вычисления (c) Эмуляция классических вычислений. Алгоритм Саймона (a) Квантовый параллелизм

Из истории математики Первой достаточно объемной книгой, в которой арифметика излагалась независимо от геометрии, было Введение в арифметику Никомаха (ок нэ) В истории арифметики её роль сравнима с ролью

Краткое введение в начала элементарной теории чисел Денис Кириенко Летняя компьютерная школа, 1 января 2009 года Целочисленное деление Пусть дано два целых числа a и b, b 0. Целочисленным частным от деления

Тема 1-9: Многочлены. Построение кольца многочленов. Теория делимости. Производная А. Я. Овсянников Уральский федеральный университет Институт математики и компьютерных наук кафедра алгебры и дискретной

Алгебраические уравнения где Определение. Алгебраическим называется уравнение вида 0, P () 0, некоторые действительные числа. 0 0 При этом переменная величина называется неизвестным, а числа 0, коэффициентами

Лекция 6 Элементы теории чисел 1 Задача. Продолжите числовой ряд 1, 3, 5, 7, 1, 3, 5, 7, 11 1, 11, 101, 1001, 1, 11, 101, 1001, 1011, 2 Арифметика целых чисел Использует целые числа: Z = {, -2, -1, 0,

Многочлены Многочленом с одной переменной х степени n называют выражение вида, где - любые числа, называемые коэффициентами многочлена, причем называют старшим коэффициентом многочлена Если вместо переменной

1 2 Содержание. 1. Введение. 4-6 1.1. Аннотация...4 1.2. Проблема 4 1.3. Цель работы 5 1.4. Гипотеза..5 1.5. Предмет исследования... 5 1.6. Объект исследования. 5 1.7. Новизна... 5-6 1.8. Методы исследования...6

8.3, 8.4.2 класс, Математика (учебник Макарычев) 2018-2019 уч.год Тема модуля «Целые числа. Делимость чисел. Степень с целым показателем» В тесте проверяются теоретическая и практическая части. ТЕМА Знать

Лекция ИНТЕГРИРОВАНИЕ РАЦИОНАЛЬНЫХ ДРОБЕЙ Рациональные дроби Интегрирование простейших рациональных дробей Разложение рациональной дроби на простейшие дроби Интегрирование рациональных дробей Рациональные

Www.cryptolymp.ru XIX Межрегиональная олимпиада школьников по математике и криптографии (11 класс) Решение задачи 1 Сначала заметим, что если N pq, где p и q простые числа, то количество натуральных чисел,

Глава Целые числа Теория делимости Целыми называются числа, -3, -, -, 0, 3, те натуральные числа, 3, 4, а также нуль и отрицательные числа -, -, -3, -4, Множество всех целых чисел обозначается через

Министерство образования и науки РФ Уральский государственный экономический университет Ю. Б. Мельников Многочлены Раздел электронного учебника для сопровождения лекции Изд. 4-е, испр. и доп. e-mail: [email protected],

{тригонометрический ряд тригонометрическая система примеры - разложение на интервале [ -l; l ] для функций произвольного периода - неполные ряды разложение по синусам и косинусам четные и нечетные продолжения}

Теоретическая информатика II Лекция 5. Целочисленные алгоритмы: расширенный алгоритм Евклида, обратный элемент по модулю, возведение в степень по модулю. Криптография с открытым ключом, протокол RSA. Вероятностная

5. Коды Боуза-Чоудхури-Хоквингема Корректирующие свойства циклических кодов могут быть определены на основе двух теорем . Теорема 1. Для любых m и t существует циклический код длиной n = 2 m 1, с кратностью

МОДУЛЬНАЯ АРИФМЕТИКА В некоторых приложениях удобно выполнять арифметические операции над целыми числами, заданными в так называемом модульном представлении Это представление предполагает, что целое число

МАТЕМАТИКА ЕГЭ 00 Корянов А.Г. Задания С г. Брянск Замечания и пожелания направляйте по адресу: [email protected] УРАВНЕНИЯ И НЕРАВЕНСТВА В ЦЕЛЫХ ЧИСЛАХ (от учебных задач до олимпиадных задач) Линейные

2.22. Вынесите за скобки общий множитель (n натуральное число): 1) x n + 3 + x n ; 3) z 3n - z n ; 2) y n + 2 - y n - 2, n > 2; 4) 5 n + 4 + 2 5 n + 2-3 5 n + 1. 2.23. Каждому числу поставили в соответствие

ЛЕКЦИЯ 15 ПРОСТЫЕ ЧИСЛА Натуральное число p, больше единицы называется простым, если оно делится нацело только на 1 и на себя. Теорема (Эвклид). Множество простых чисел бесконечно. Обозначим через π(x)

Тема 3. Элементы алгебраической и аналитической теории чисел Теоретический материал 1. Цепные дроби. Конечной цепной дробью называется выражение a +, (1) где a - целое число, a, i > 0, натуральные числа,

Http://vk.ucoz.et/ Операции над многочленами k a k Многочленом (полиномом) степени k называется функция вида a, где переменная, a - числовые коэффициенты (=,.k), и. Любое ненулевое число можно рассматривать

Пензенский государственный педагогический университет имени В. Г. Белинского М. В. Глебова В. Ф. Тимербулатова ПРАКТИЧЕСКИЕ ЗАНЯТИЯ ПО АЛГЕБРЕ МНОГОЧЛЕНОВ Учебно-методическое пособие Пенза Печатается по

ДЕЛИМОСТЬ ЦЕЛЫХ ЧИСЕЛ С ОСТАТКОМ Пусть m целое число, а n натуральное число Если m > n и m не делится на n нацело, то возможно деление m на n с остатком Определение 3 Для любого целого числа m и любого

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

ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля (поля Галуа) I 1 / 88 Часть I Конечные поля (поля Галуа) I ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля (поля Галуа) I 2 / 88 Поля вычетов по модулю простого числа

5 Алгебраические структуры 6 Определение Бинарная операция на множестве S есть отображение S S в S То есть, является правилом, которое каждой упорядоченной паре элементов из S ставит в соответствие некоторый

/Е Э лементы теории чисел и. рочев 28 августа 2018 г. Оглавление Оглавление i 1 Целые числа 1 1.1 Вводные задачи....................................... 1 1.2 Наибольший общий делитель..............................

Глава Целые, рациональные и действительные числа. Деление с остатком. Каждое из чисел ±23, ±4 разделите с остатком на каждое из чисел ±5. 2. Найдите все положительные делители числа 42. 3. Сейчас 3 часов.

Дифференциальные уравнения лекция 4 Уравнения в полных дифференциалах. Интегрирующий множитель Лектор Шерстнёва Анна Игоревна 9. Уравнения в полных дифференциалах Уравнение d + d = 14 называется уравнением

Тема. Основы элементарной теории чисел и приложения-. Первообразные корни, индексы. Теоретический материал Пусть а, m натуральные взаимно простые числа, причем m, тогда, согласно теореме Эйлера, a m)

Кафедра математики и информатики Элементы высшей математики Учебно-методический комплекс для студентов СПО, обучающихся с применением дистанционных технологий Модуль Теория пределов Составитель: доцент

Раздел 2. Теоретико-численные методы в криптографии Задание на самостоятельную работу Изучить алгоритмы, которые широко применяются в криптографии. Элементы теории чисел: расширенный алгоритм Евклида;

Тематический план составлен на основе программного материала 206-207 уч.года по учебнику «Алгебра 8» под ред. А.Г.Мордковича с учетом рекомендованного обязательного минимума содержания образования Тема

Лекция 2. Свойства биномиальных коэффициентов. Подсчет сумм и метод производящих функций (конечный случай). Полиномиальные коэффициенты. Оценки биномиальных и полиномиальных коэффициентов. Оценки сумм

С глубокой древности работа с числами подразделялась на две различные области: одна касалась непосредственно свойств чисел, другая была связана с техникой счета. Под «арифметикой» во многих странах обычно имеется ввиду именно эта последняя область, которая несомненно является старейшей отраслью математики.

По-видимому, наибольшую трудность у древних вычислителей вызывала работа с дробями. Об этом можно судить по папирусу Ахмеса (называемому также папирусом Ринда), древнеегипетскому сочинению по математике, датируемому примерно 1650 до н.э. Все дроби, упоминаемые в папирусе, за исключением 2/3, имеют числители, равные 1. Трудность обращения с дробями заметна и при изучении древневавилонских клинописных табличек. И древние египтяне, и вавилоняне, по-видимому, производили вычисления с помощью некоторой разновидности абака. Наука о числах получила у древних греков существенное развитие начиная с Пифагора, около 530 до н.э. Что же касается непосредственно техники вычисления, то в этой области греками было сделано гораздо меньше.

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

Индийская система счисления и первые арифметические алгоритмы были заимствованы арабами. Самый ранний из дошедших до нас арабских учебников арифметики был написан аль-Хорезми около 825. В нем широко используются и объясняются индийские цифры. Позднее этот учебник был переведен на латынь и оказал значительное влияние на Западную Европу. Искаженный вариант имени аль-Хорезми дошел до нас в слове «алгоризм», которое при дальнейшем смешении с греческим словом аритмос превратилось в термин «алгоритм».

Индо-арабская арифметика стала известна в Западной Европе в основном благодаря сочинению Л.Фибоначчи Книга абака (Liber abaci , 1202). Метод абацистов предлагал упрощения, подобные использованию нашей позиционной системы, во всяком случае для сложения и умножения. Абацистов сменили алгоритмики, которые использовали нуль и арабский метод деления и извлечения квадратного корня. Один из первых учебников арифметики, автор которого нам неизвестен, вышел в Тревизо (Италия) в 1478. В нем речь шла о расчетах при совершении торговых сделок. Этот учебник стал предшественником многих появившихся впоследствии учебников арифметики. До начала 17 в. в Европе было опубликовано более трехсот таких учебников. Арифметические алгоритмы за это время были существенно усовершенствованы. В 16–17 вв. появились символы арифметических операций, такие как =, +, -, ґ, ё и .

Механизация арифметических вычислений.

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

На самом деле простейшие счетные устройства существовали до появления современной арифметики, ибо в древности элементарные арифметические операции производились на абаке (в России с этой целью использовались счеты). Простейшим современным вычислительным устройством можно считать логарифмическую линейку, представляющую собой две скользящие одна вдоль другой логарифмические шкалы, что позволяет производить умножение и деление, суммируя и вычитая отрезки шкал. Изобретателем первой механической суммирующей машины принято считать Б.Паскаля (1642). Позднее в том же столетии Г.Лейбниц (1671) в Германии и С.Морленд (1673) в Англии изобрели машины для выполнения умножения. Эти машины стали предшественницами настольных вычислительных устройств (арифмометров) 20 в., позволявших быстро и точно производить операции сложения, вычитания, умножения и деления.

В 1812 английский математик Ч.Бэббидж приступил к созданию проекта машины для вычисления математических таблиц. Хотя работа над проектом продолжалась долгие годы, она так и осталась незавершенной. Тем не менее проект Бэббиджа послужил стимулом к созданию современных электронных вычислительных машин, первые образцы которых появились около 1944. Быстродействие этих машин поражало воображение: с их помощью за минуты или часы удавалось решить задачи, ранее требовавшие многих лет непрерывных вычислений даже с применением арифмометров.

Целые положительные числа.

Пусть A и B – два конечных множества, не имеющие общих элементов, и пусть A содержит n элементов, а B содержит m элементов. Тогда множество S , состоящее из всех элементов множеств A и B , взятых вместе, является конечным множеством, содержащим, скажем, s элементов. Например, если А состоит из элементов {a , b , c }, множество В – из элементов {x , y }, то множество S = A + B и состоит из элементов {a , b , c , x , y }. Число s называется суммой чисел n и m , и мы записываем это так: s = n + m . В этой записи числа n и m называются слагаемыми , операция нахождения суммы – сложением . Символ операции «+» читается как «плюс». Множество P , состоящее из всех упорядоченных пар, в которых первый элемент выбран из множества A , а второй – из множества B , является конечным множеством, содержащим, скажем, p элементов. Например, если, как и прежде, A = {a , b , c }, B = {x , y }, то P = A ґB = {(a ,x ), (a ,y ), (b ,x ), (b ,y ), (c ,x ), (c ,y )}. Число p называется произведением чисел a и b , и мы записываем это так: p = a ґb или p = aЧb . Числа a и b в произведении называются множителями , операция нахождения произведения – умножением . Символ операции ґ читается как «умноженное на».

Можно показать, что из этих определений следуют приводимые ниже фундаментальные законы сложения и умножения целых чисел:

– закон коммутативности сложения: a + b = b + a ;

– закон ассоциативности сложения: a + (b + c ) = (a + b ) + c ;

– закон коммутативности умножения: a ґb = b ґa ;

– закон ассоциативности умножения: a ґ(b ґc ) = (a ґb )ґc ;

– закон дистрибутивности: a ґ(b + c )= (a ґb ) + (a ґc ).

Если a и b – два положительных целых числа и если существует положительное целое число c , такое, что a = b + c , то мы говорим, что a больше b (это записывается так: a > b ), или что b меньше a (это записывается так: b). Для любых двух чисел a и b выполняется одно из трех соотношений: либо a = b , либо a > b , либо a .

Первые два фундаментальных закона говорят о том, что сумма двух или большего числа слагаемых не зависит от того, как они сгруппированы и в каком порядке они расположены. Аналогично, из третьего и четвертого законов следует, что произведение двух или большего числа множителей не зависит от того, как сгруппированы множители и каков их порядок. Эти факты известны как «обобщенные законы коммутативности и ассоциативности» сложения и умножения. Из них следует, что при написании суммы нескольких слагаемых или произведения нескольких множителей порядок слагаемых и множителей несуществен и можно опустить скобки.

В частности, повторная сумма a + a + ... + a из n слагаемых равна n ґa . Повторное произведение a ґa ґ ... ґa из n множителей условились обозначать a n ; число a называется основанием , а число n – показателем повторного произведения , само повторное произведение – n-й степенью числа a . Эти определения позволяют установить следующие фундаментальные законы для показателей степени:

Еще одно важное следствие из определений: a ґ1 = a для любого целого числа a , причем 1 – единственное целое число, обладающее этим свойством. Число 1 называется единицей .

Делители целых чисел.

Если a , b , c – целые числа и a ґb = c , то a и b являются делителями числа c . Так как a ґ1 = a для любого целого числа a , мы заключаем, что 1 – делитель любого целого числа и что любое целое число есть делитель самого себя. Любой делитель целого числа a , отличный от 1 или a , получил название собственного делителя числа a .

Любое целое число, отличное от 1 и не имеющее собственных делителей, называется простым числом . (Примером простого числа может служить число 7.) Целое число, имеющее собственные делители, называется составным числом . (Например, число 6 составное, так как 2 делит 6.) Из сказанного следует, что множество всех целых чисел подразделяется на три класса: единица, простые числа и составные числа.

В теории чисел есть очень важная теорема, которая утверждает, что «любое целое число может быть представлено в виде произведения простых чисел, и с точностью до порядка множителей такое представление единственно». Эта теорема известна как «основная теорема арифметики». Она показывает, что простые числа служат теми «кирпичиками», из которых с помощью умножения можно построить все целые числа, отличные от единицы.

Если задано некоторое множество целых чисел, то наибольшее целое число, которое является делителем каждого числа, входящего в это множество, называется наибольшим общим делителем данного множества чисел; наименьшее целое число, делителем которого служит каждое число из данного множества, называется наименьшим общим кратным данного множества чисел. Так, наибольший общий делитель чисел 12, 18 и 30 равен 6. Наименьшее общее кратное тех же самых чисел равно 180. Если наибольший общий делитель двух целых чисел a и b равен 1, то числа a и b называются взаимно простыми . Например, числа 8 и 9 – взаимно простые, хотя ни одно из них не является простым.

Положительные рациональные числа.

Как мы видели, целые числа являются абстракциями, возникающими из процесса пересчета конечных наборов предметов. Однако для потребностей повседневной жизни целых чисел оказывается недостаточно. Например, при измерении длины крышки стола принятая единица измерения может оказаться слишком большой и не укладываться целое число раз в измеряемой длине. Чтобы справиться с подобной трудностью, с помощью т.н. дробных (т.е., буквально, «поломанных») чисел вводится меньшая единица длины. Если d – некоторое целое число, то дробная единица 1/d определяется свойством d ґ1/d = 1, и если n – целое число, то n ґ1/d мы записываем просто как n /d . Такие новые числа получили название «обыкновенных» или «простых» дробей. Целое число n называется числителем дроби, а число d – знаменателем . Знаменатель показывает, на сколько равных долей разделили единицу, а числитель показывает, сколько таких долей взяли. Если n d, дробь называется правильной; если же n = d или n > d , то – неправильной. Целые числа рассматриваются как дроби с знаменателем, равным 1; например, 2 = 2/1.

Так как дробь n /d можно интерпретировать как результат деления n единиц на d равных долей и взятия одной из таких долей, дробь можно рассматривать как «частное» или «отношение» двух целых чисел n и d , а черту дроби понимать как знак деления. Поэтому дроби (в т.ч. и целые числа как частный случай дробей) обычно называют рациональными числами (от лат. ratio – отношение).

Две дроби n /d и (k ґn )/(k ґd ), где k – целое число, можно рассматривать как равные; например, 4/6 = 2/3. (Здесь n = 2, d = 3 и k = 2.) Это обстоятельство известно как «основное свойство дроби»: значение любой дроби не изменится, если числитель и знаменатель дроби умножить (или разделить) на одно и то же число. Отсюда следует, что любую дробь можно записать как отношение двух взаимно простых чисел.

Из предложенной выше интерпретации дроби также следует, что в качестве суммы двух дробей n /d и m /d , имеющих один и тот же знаменатель, следует принять дробь (n + m )/d . При сложении дробей с разными знаменателями нужно сначала преобразовать их, пользуясь основным свойством дроби, в эквивалентные дроби с одинаковым (общим) знаменателем. Например, n 1 /d 1 = (n 1 Чd 2)/(d 1 Чd 2) и n 2 /d 2 = (n 2 Чd 1)/(d 1 Чd 2), откуда

Можно было бы поступить иначе и сначала найти наименьшее общее кратное, скажем, m , знаменателей d 1 и d 2 . Тогда существуют целые числа k 1 и k 2 , такие, что m = k 1 Чd 1 = k 2 Чd 2 , и мы получаем:

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

Произведение двух дробей n 1 /d 1 и n 2 /d 2 принимается равным дроби (n 1 Чn 2)/(d 1 Чd 2).

Восемь фундаментальных законов, приведенных выше для целых чисел, справедливы и в том случае, если под a , b , c понимать произвольные положительные рациональные числа. Кроме того, если даны два положительных рациональных числа n 1 /d 1 и n 2 /d 2 , то мы говорим, что n 1 /d 1 > n 2 /d 2 тогда и только тогда, когда n 1 Чd 2 > n 2 Чd 1 .

Положительные действительные числа.

Применение чисел для измерения длин отрезков прямых наводит на мысль, что для любых двух данных отрезков прямых AB и CD должен существовать некоторый отрезок UV , возможно, очень малый, который можно было бы отложить целое число раз в каждом из отрезков AB и CD . Если такая общая единица измерения длины UV существует, то отрезки AB и CD называются соизмеримыми. Уже в древности пифагорейцы знали о существовании несоизмеримых отрезков прямых. Классический пример – сторона квадрата и его диагональ. Если принять сторону квадрата за единицу длины, то не найдется такого рационального числа, которое могло бы быть мерой диагонали этого квадрата. Убедиться в этом можно, рассуждая от противного. Действительно, предположим, что рациональное число n /d есть мера диагонали. Но тогда отрезок 1/d можно было бы отложить n раз на диагонали и d раз на стороне квадрата вопреки тому, что диагональ и сторона квадрата несоизмеримы. Следовательно, независимо от выбора единицы длины не все отрезки прямых имеют длины, выражаемые рациональными числами. Чтобы все отрезки прямой можно было измерять с помощью некоторой единицы длины, система счисления должна быть расширена таким образом, чтобы она включала числа, представляющие результаты измерения длин отрезков прямых, несоизмеримых с выбранной единицей длины. Эти новые числа называются положительными иррациональными числами. Последние вместе с положительными рациональными числами образуют более широкое множество чисел, элементы которого называются положительными действительными числами.

Если OR – горизонтальная полупрямая, исходящая из точки O , U – точка на OR , отличная от начала координат O , и OU выбран в качестве единичного отрезка, то каждой точке P на полупрямой OR можно поставить в соответствие единственное положительное действительное число p , выражающее длину отрезка OP . Таким образом мы устанавливаем взаимно однозначное соответствие между положительными действительными числами и точками, отличными от O , на полупрямой OR . Если p и q – два положительных действительных числа, соответствующих точкам P и Q на OR , то мы пишем p > q , p = q или p в зависимости от того, расположена точка P справа от точки Q на OR , совпадает с Q или расположена слева от Q .

Введение положительных иррациональных чисел существенно расширило сферу применимости арифметики. Например, если a – любое положительное действительное число и n – любое целое число, то существует единственное положительное действительное число b , такое, что b n = a . Это число b называется корнем n -й степени из a и записывается как , где символ по своим очертаниям напоминает латинскую букву r , с которой начинается латинское слово radix (корень) и называется радикалом . Можно показать, что

Эти соотношения известны как основные свойства радикалов.

С практической точки зрения очень важно, что любое положительное иррациональное число можно сколь угодно точно аппроксимировать положительным рациональным числом. Это означает, что если r – положительное иррациональное число и e – сколь угодно малое положительное рациональное число, то можно найти положительные рациональные числа a и b , такие, что a и b . Например, число иррационально. Если выбрать e = 0,01, то ; если же выбрать e = 0,001, то .

Индо-арабская система счисления.

Алгоритмы, или схемы вычислений, арифметики зависят от используемой системы счисления. Совершенно очевидно, например, что методы вычислений, придуманные для римской системы счисления, могут отличаться от алгоритмов, изобретенных для действующей ныне индо-арабской системы. Более того, некоторые системы счисления могут оказаться совсем неподходящими для построения арифметических алгоритмов. Исторические данные свидетельствуют, что до принятия индо-арабской системы обозначения чисел вообще не существовало каких-либо алгоритмов, позволявших достаточно легко с помощью «карандаша и бумаги» выполнять сложение, вычитание, умножение и деление чисел. За долгие годы существования индо-арабской системы были разработаны специально к ней приспособленные многочисленные алгоритмические процедуры, так что наши современные алгоритмы являются продуктом целой эпохи развития и усовершенствования .

В индо-арабской системе счисления каждая запись, обозначающая число, представляет собой набор из десяти основных символов 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, называемых цифрами. Например, индо-арабское обозначение числа четыреста двадцать три имеет вид последовательности цифр 423. Значение цифры в индо-арабской записи числа определяется ее местом, или позицией, в последовательности цифр, образующих эту запись. В приведенном нами примере цифра 4 означает четыре сотни, цифра 2 – два десятка и цифра 3 – три единицы. Очень важную роль играет цифра 0 (нуль), используемая для заполнения пустых позиций; например, запись 403 означает число четыреста три, т.е. отсутствуют десятки. Если a , b , c , d , e означают отдельные цифры, то в индо-арабской системе abcde означает сокращенную запись целого числа

Так как каждое целое число допускает единственное представление в виде

где n – целое число, а a 0 , a 1 ,..., a n – цифры, мы заключаем, что в данной системе счисления каждое целое число можно представить единственным способом.

Индо-арабская система счисления позволяет сжато записывать не только целые, но и любые положительные действительные числа. Введем обозначение 10 -n для 1/10 n , где n – произвольное положительное целое число. Тогда, как можно показать, любое положительное действительное число представимо, причем единственным образом, в виде

Эту запись можно сжать, записав в виде последовательности цифр

где знак, называемый десятичной запятой, между a 0 и b 1 указывает, где начинаются отрицательные степени числа 10 (в некоторых странах с этой целью используется точка). Такой способ записи положительного действительного числа получил название десятичного разложения, а дробь, представленная в виде своего десятичного разложения, – десятичной .

Можно показать, что для положительного рационального числа десятичное разложение после запятой либо обрывается (например, 7/4 = 1,75), либо повторяется (например, 6577/1980 = 3,32171717...). Если число иррационально, то его десятичное разложение не обрывается и не повторяется. Если десятичное разложение иррационального числа на каком-то знаке после запятой оборвать, мы получим его рациональное приближение. Чем дальше справа от запятой расположен знак, на котором мы обрываем десятичное разложение, тем лучше рациональное приближение (тем меньше ошибка).

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

Названия чисел.

Названия чисел в индо-арабской системе строятся по определенным правилам. Наиболее употребительный способ наименования чисел заключается в том, что число прежде всего делят на группы из трех цифр справа налево. Эти группы называются «периодами». Первый период называется периодом «единиц», второй – периодом «тысяч», третий – периодом «миллионов» и т.д., как показано на следующем примере:

Каждый период читается так, как если бы он был трехзначным числом. Например, период 962 читается как «девятьсот шестьдесят два». Чтобы прочитать число, состоящее из нескольких периодов, прочитывается группа цифр в каждом периоде, начиная с самого левого и далее по порядку слева направо; после каждой группы следует название периода. Например, приведенное выше число читается как «семьдесят три триллиона восемьсот сорок два миллиарда девятьсот шестьдесят два миллиона пятьсот тридцать две тысячи семьсот девяносто восемь». Обратите внимание на то, что при чтении и записи целых чисел союз «и» обычно не используется. Название разряда единиц опускается. За триллионами следуют квадриллионы, квинтиллионы, секстиллионы, септиллионы, октиллионы, ноналлионы, дециллионы. Каждый период имеет значение, в 1000 раз превышающее значение предыдущего.

В индо-арабской системе принято придерживаться следующей процедуры чтения цифр, стоящих справа от десятичной запятой. Здесь позиции называются (по порядку слева направо): «десятые», «сотые», «тысячные», «десятитысячные» и т.д. Правильная десятичная дробь читается так, как если бы цифры после десятичной запятой образовывали целое число, после чего добавляется название позиции последней справа цифры. Например, 0,752 читается как «семьсот пятьдесят две тысячных». Смешанное десятичное число читается путем объединения правила наименования целых чисел с правилом наименования правильных десятичных дробей. Например, 632,752 читается как «шестьсот тридцать две целых семьсот пятьдесят две тысячных». Обратите внимание на слово «целых», произносимое перед десятичной запятой. В последние годы десятичные числа все чаще читают более просто, например, 3,782 как «три запятая семьсот восемьдесят два».

Сложение.

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

Рассмотрим задачу на сложение: вычислить 279,8 + 5,632 + 27,54:

Сначала мы суммируем одинаковые степени числа 10. Число 19Ч10 –1 разбивается по дистрибутивному закону на 9Ч10 –1 и 10Ч10 –1 = 1. Единицу мы переносим влево и прибавляем к 21, что дает 22. В свою очередь, число 22 мы разбиваем на 2 и 20 = 2Ч10. Число 2Ч10 переносим влево и прибавляем к 9Ч10, что дает 11Ч10. Наконец, 11Ч10 разбиваем на 1Ч10 и 10Ч10 = 1Ч10 2 , 1Ч10 2 переносим влево и прибавляем к 2Ч10 2 , что дает 3Ч10 2 . Окончательная сумма оказывается равной 312,972.

Ясно, что проделанные вычисления можно представить в более сжатой форме, заодно использовав ее как пример алгоритма сложения, которому учат в школе. Для этого все три числа мы выписываем одно под другим так, чтобы десятичные запятые оказались на одной вертикали:

Начав справа, находим, что сумма коэффициентов при 10 –3 равна 2, что и записываем в соответствующем столбце под чертой. Сумма коэффициентов при 10 –2 равна 7, что также записываем в соответствующем столбце под чертой. Сумма коэффициентов при 10 –1 равна 19. Число 9 мы записываем под чертой, а 1 переносим в предыдущий столбец, где стоят единицы. С учетом этой единицы сумма коэффициента в этом столбце оказывается равной 22. Мы записываем одну двойку под чертой, а другую переносим в предыдущий столбец, где стоят десятки. С учетом перенесенной двойки сумма коэффициентов в этом столбце равна 11. Одну единицу мы записываем под чертой, а другую переносим в предыдущий столбец, где стоят сотни. Сумма коэффициентов в этом столбце оказывается равной 3, что и записываем под чертой. Требуемая сумма равна 312,972.

Вычитание.

Вычитание – это действие, обратное сложению. Если три положительных действительных числа a , b , c связаны между собой так, что a + b = c , то мы записываем a = c – b , где символ «-» читается как «минус». Нахождение числа a по известным числам b и c называется «вычитанием». Число c называется уменьшаемым, число b – «вычитаемым», а число a – «разностью». Поскольку мы имеем дело с положительными действительными числами, должно выполняться условие c > b .

Рассмотрим пример на вычитание: вычислить 453,87 – 82,94.

Прежде всего, заимствуя в случае необходимости единицу слева, мы преобразуем разложение уменьшаемого так, чтобы его коэффициент при любой степени числа 10 был больше коэффициента вычитаемого при той же степени. Из 4Ч10 2 мы заимствуем 1Ч10 2 = 10Ч10, прибавляя последнее число к следующему члену разложения, что дает 15Ч10; аналогично мы заимствуем 1Ч10 0 , или 10Ч10 –1 , и прибавляем это число к предпоследнему члену разложения. После этого мы получаем возможность произвести вычитание коэффициентов при одинаковых степенях числа 10 и без труда находим разность 370,93.

Запись операций вычитания можно представить в более сжатом виде и получить пример алгоритма вычитания, изучаемого в школе. Запишем вычитаемое под уменьшаемым так, чтобы их десятичные запятые оказались на одной вертикали. Начав справа, найдем, что разность коэффициентов при 10 –2 равна 3, и это число запишем в том же столбце под чертой. Так как в следующем столбце слева мы не можем вычесть 9 из 8, мы изменяем тройку в положении единиц уменьшаемого на двойку и рассматриваем число 8 в позиции десятых как 18. После вычитания 9 из 18 мы получаем 9 и т.д., т.е.

Умножение.

Рассмотрим сначала т.н. «короткое» умножение – умножение положительного действительного числа на одно из однозначных чисел 1, 2, 3, 4, 5, 6, 7, 8, 9, например, 32,67ґ4. Пользуясь законом дистрибутивности, а также законами ассоциативности и коммутативности умножения, мы получаем возможность разбивать множители на части и располагать их более удобным образом. Например,

Эти вычисления можно записать более компактно следующим образом:

Процесс сжатия можно продолжить. Запишем множитель 4 под множимым 32,67, как указано:

Так как 4ґ7 = 28, мы записываем под чертой цифру 8, а 2 помещаем над цифрой 6 множимого. Далее, 4ґ6 = 24, что с учетом перенесенной из столбца справа дает 26. Цифру 6 мы записываем под чертой, а 2 записываем над цифрой 2 множимого. Затем мы получаем 4ґ2 = 8, что в сочетании с перенесенной двойкой дает 10. Цифру 0 мы подписываем под чертой, а единицу – над цифрой 3 множимого. Наконец, 4ґ3 = 12, что с учетом перенесенной единицы дает 13; число 13 записываем под чертой. Поставив десятичную запятую, получаем ответ: произведение равно 130,68.

«Длинное» умножение – это просто неоднократно повторенное «короткое» умножение. Рассмотрим, например, умножение числа 32,67 на число 72,4. Расположим множитель под множимым, как указано:

Производя справа налево короткое умножение, мы получаем первое частное произведение 13,068, второе – 65,34 и третье – 2286,9. По закону дистрибутивности, произведение, которое требуется найти, есть сумма этих частных произведений, или 2365,308. В письменной записи десятичная запятая в частных произведениях опускается, но их нужно правильно располагать «ступеньками», чтобы затем просуммировать и получить полное произведение. Число знаков после десятичной запятой в произведении равно сумме числа знаков после запятых в множимом и множителе.

Деление.

Деление – операция, обратная умножению; подобно тому, как умножение заменяет неоднократно повторенное сложение, деление заменяет неоднократно повторенное вычитание. Рассмотрим, например, такой вопрос: сколько раз 3 содержится в 14? Повторяя операцию вычитания 3 из 14, мы находим, что 3 «входит» в 14 четыре раза, и еще «остается» число 2, т.е.

Число 14 называется делимым , число 3 – делителем , число 4 – частным и число 2 – остатком . Словами получившееся соотношение можно выразить так:

делимое = (делитель ґ частное) + остаток,

0 Ј остаток

Чтобы найти частное и остаток от деления 1400 на 3 с помощью многократного вычитания 3, потребовалось бы затратить немало времени и труда. Процедуру можно было бы существенно ускорить, если сначала вычитать из 1400 по 300, затем из остатка по 30 и, наконец, по 3. После четырехкратного вычитания 300 мы получили бы в остатке 200; после шестикратного вычитания из 200 числа 30 остаток оказался бы равным 20; наконец, после шестикратного вычитания из 20 числа 3 мы получим остаток 2. Следовательно,

Частное и остаток, которые требовалось найти, равны, соответственно, 466 и 2. Вычисления можно организовать и затем последовательно подвергнуть сжатию следующим образом:

Приведенные выше рассуждения применимы, если делимое и делитель – любые положительные действительные числа, выраженные в десятичной системе. Проиллюстрируем это на примере 817,65ё23,7.

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

Определим, сколько раз делитель содержится в трехзначном числе 817, первой части делимого, которую мы делим на делитель. Так как по оценкам он содержится три раза, мы умножаем 237 на 3 и произведение 711 вычитаем из 817. Разность 106 меньше делителя. Это означает, что число 237 входит в пробное делимое не более трех раз. Цифра 3, написанная под цифрой 2 делителя ниже горизонтальной черты, – первая цифра частного, которое требуется найти. После того, как мы снесем вниз следующую цифру делимого, получится следующее пробное делимое 1066, и надо определить, сколько раз делитель 237 укладывается в числе 1066; предположим, что 4 раза. Умножаем делитель на 4 и получаем произведение 948, которое вычитаем из 1066; разность оказывается равной 118, что означает, что следующая цифра частного равна 4. Затем мы сносим следующую цифру делимого и повторяем всю процедуру, описанную выше. На этот раз оказывается, что пробное делимое 1185 точно (без остатка) делится на 237 (остаток от деления наконец оказывается равным 0). Отделив десятичной запятой в частном столько же знаков, сколько их отделено в делимом (напомним, что ранее мы десятичную запятую переносили), получим ответ: частное равно 34,5.

Дроби.

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

Сложение дробей с одним и тем же знаменателем производится путем сложения числителей, например,

1/16 + 5/16 + 7/16 = (1 + 5 + 7)/16 = 13/16.

Если дроби имеют различные знаменатели, то предварительно их необходимо привести к общему знаменателю, т.е. превратить в дроби с одинаковыми знаменателями. Для этого мы находим наименьший общий знаменатель (наименьшее число, кратное каждому из данных знаменателей). Например, при сложении 2/3, 1/6 и 3/5 наименьший общий знаменатель равен 30:

Суммируя, получаем

20/30 + 5/30 + 18/30 = 43/30.

Вычитание дробей производится так же, как их сложение. Если знаменатели одинаковы, то вычитание сводится к вычитанию числителей: 10/13 – 2/13 = 8/13; если дроби имеют различные знаменатели, то предварительно необходимо привести их к общему знаменателю:

7/8 – 3/4 = 7/8 – 6/8 = (7 – 6)/8 = 1/8.

При умножении дробей их числители и знаменатели умножаются отдельно. Например,

5/6ґ4/9 = 20/54 = 10/27.

Чтобы разделить одну дробь на другую, необходимо умножить первую дробь (делимое) на дробь, обратную второй (делителю) (чтобы получить обратную дробь, надо поменять местами числитель и знаменатель исходной дроби), т.е. (n 1 /d 1)ё(n 2 /d 2) = (n 1 Чd 2)/(d 1 Чn 2). Например,

3/4ё7/8 = 3/4ґ8/7 = 24/28 = 6/7.

Смешанное число представляет собой сумму (или разность) целого числа и дроби, например, 4 + 2/3 или 10 – 1/8. Так как целое число можно рассматривать как дробь с знаменателем, равным 1, смешанное число есть не что иное, как сумма (или разность) двух дробей. Например,

4 + 2/3 = 4/1 + 2/3 = 12/3 + 2/3 = 14/3.

Сложной называется дробь, имеющая дробь либо в числителе, либо в знаменателе, либо в числителе и знаменателе. Такую дробь можно превратить в простую:

Квадратный корень.

Если n r , такое, что r 2 = n . Число r называется квадратным корнем из n и обозначается . В школе учат извлекать квадратные корни двумя способами.

Первый способ более популярен, поскольку он проще и его легче применять; вычисления по этому методу легко реализуются на настольном калькуляторе и обобщаются на случай кубических корней и корней более высокой степени. Основан метод на том, что если r 1 – приближение к корню , то r 2 = (1/2)(r 1 + n /r 1) – более точная аппроксимация корня.

Проиллюстрируем процедуру на примере вычисления квадратного корня из какого-нибудь числа, заключенного между 1 и 100, скажем, числа 40. Так как 6 2 = 36, а 7 2 = 49, мы заключаем, что 6 – наилучшее приближение к в целых числах. Более точное приближение к получается из 6 следующим образом. Разделив 40 на 6, получим 6,6 (с округлением до первого после запятой четного числа десятых). Чтобы получить второе приближение к , усредним два числа 6 и 6,6 и получим 6,3. Повторив процедуру, получим еще лучшее приближение. Разделив 40 на 6,3, находим число 6,350, и третье приближение оказывается равным (1/2)(6,3 + 6,350) = 6,325. Еще одно повторение дает 40ё6,325 = 6,3241106, и четвертая аппроксимация оказывается равной (1/2)(6,325 + 6,3241106) = 6,3245553. Процесс может продолжаться сколь угодно долго. В общем случае каждое следующее приближение может содержать вдвое больше цифр, чем предыдущее. Так, в нашем примере, поскольку первое приближение, целое число 6, содержит только одну цифру, мы можем удерживать во втором приближении два знака, в третьем – четыре и в четвертом – восемь.

Если число n не лежит между 1 и 100, то следует предварительно разделить (или умножить) n на некоторую степень числа 100, скажем, на k -ю, чтобы произведение оказалось в интервале от 1 до 100. Тогда квадратный корень из произведения будет находиться в интервале от 1 до 10, и после того, как он будет извлечен, мы, умножив (или разделив) полученное число на 10 k , найдем искомый квадратный корень. Например, если n = 400000, то мы сначала делим 400000 на 100 2 и получаем число 40, лежащее в интервале от 1 до 100. Как показано выше, приближенно равен 6,3245553. Умножая это число на 10 2 , получаем 632,45553 в качестве приближенного значения для , а число 0,63245553 служит приближенным значением для .

Вторая из упомянутых выше процедур основана на алгебраическом тождестве (a + b ) 2 = a 2 + (2a + b )b . На каждом шаге уже полученная часть квадратного корня принимается за a , а часть, которую еще требуется определить, – за b .

Кубический корень.

Для извлечения кубического корня из положительного действительного числа существуют алгоритмы, аналогичные алгоритмам извлечения квадратного корня. Например, чтобы найти кубический корень из числа n , сначала мы аппроксимируем корень некоторым числом r 1 . Затем строим более точное приближение r 2 = (1/3)(2r 1 + n /r 1 2), которое в свою очередь уступает место еще более точному приближению r 3 = (1/3)(2r 2 + n /r 2 2) и т.д. Процедура построения все более точных приближений корня может продолжаться сколь угодно долго.

Рассмотрим, например, вычисление кубического корня из числа, заключенного между 1 и 1000, скажем, числа 200. Так как 5 3 = 125 и 6 3 = 216, мы заключаем, что 6 – ближайшее к кубическому корню из 200 целое число. Следовательно, выбираем r 1 = 6 и последовательно вычисляем r 2 = 5,9, r 3 = 5,85, r 4 = 5,8480. В каждом приближении, начиная с третьего, разрешается удерживать число знаков, которое на единицу меньше удвоенного числа знаков в предыдущем приближении. Если же число, из которого требуется извлечь кубический корень, не заключено между 1 и 1000, то предварительно его необходимо разделить (или умножить) на некоторую, скажем, k -ю, степень числа 1000 и тем самым привести в нужный интервал чисел. Кубический корень из вновь полученного числа лежит в интервале от 1 до 10. После того, как он будет вычислен, его необходимо умножить (или разделить) на 10 k , чтобы получить кубический корень из исходного числа.

Второй, более сложный, алгоритм нахождения кубического корня из положительного действительного числа основан на использовании алгебраического тождества (a + b ) 3 = a 3 + (3a 2 + 3ab + b 2)b . В настоящее время алгоритмы извлечения кубических корней, равно как и корней более высоких степеней, в средней школе не изучают, так как их легче находить с помощью логарифмов или алгебраическими методами.

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

Этот алгоритм был изложен в Началах Евклида (ок. 300 до н.э.). С его помощью вычисляется наибольший общий делитель двух целых чисел. Для случая положительных чисел он формулируется в виде процедурного правила: «Разделите большее из двух данных чисел на меньшее. Затем разделите делитель на остаток от деления и продолжайте действовать так же, пока последний делитель не разделится нацело на последний остаток. Последний из делителей и будет наибольшим общим делителем двух данных чисел».

В качестве числового примера рассмотрим два целых числа 3132 и 7200. Алгоритм в этом случае сводится к следующим действиям:

Наибольший общий делитель совпадает с последним делителем – числом 36. Объяснение просто. В нашем примере мы видим из последней строки, что число 36 делит число 288. Из предпоследней строки следует, что число 36 делит 324. Так, двигаясь от строки к строке вверх, мы убеждаемся в том, что число 36 делит 936, 3132 и 7200. Мы утверждаем теперь, что число 36 есть общий делитель чисел 3132 и 7200. Пусть g – наибольший общий делитель чисел 3132 и 7200. Так как g делит 3132 и 7200, из первой строки следует, что g делит 936. Из второй строки мы заключаем, что g делит 324. Так, спускаясь от строки к строке, мы убеждаемся в том, что g делит 288 и 36. А так как 36 – общий делитель чисел 3132 и 7200 и делится на наибольший общий их делитель, мы заключаем, что 36 и есть этот наибольший общий делитель.

Проверка.

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

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

2. Вычитание проверяется путем сложения разности с вычитаемым – должно получиться уменьшаемое. Обоснованием такого способа проверки служит определение операции вычитания.

3. Умножение можно проверить, переставив множимое и множитель. Обоснованием такого способа проверки служит закон коммутативности умножения. Можно проверить умножение, разбив множитель (или множимое) на два слагаемых, выполнив две отдельные операции умножения и сложив полученные произведения – должно получиться исходное произведение.

4. Чтобы проверить деление, надо умножить частное на делитель и к произведению прибавить остаток. Должно получиться делимое. Обоснованием такого способа проверки служит определение операции деления.

5. Проверка правильности извлечения квадратного (или кубического) корня состоит в возведении полученного числа в квадрат (или куб) – должно получиться исходное число.

Особенно простым и весьма надежным способом проверки сложения или умножения целых чисел служит прием, представляющий собой переход к т.н. «сравнениям по модулю 9». Назовем «избытком» остаток от деления на 9 суммы цифр, которыми записано данное число. Тогда относительно «избытков» можно сформулировать две теоремы: «избыток суммы целых чисел равен избытку суммы избытков слагаемых», и «избыток произведения двух целых чисел равен избытку произведения их избытков». Ниже даются примеры проверок, основанных на этой теореме:

Метод перехода к сравнениям по модулю 9 можно использовать и при проверке других арифметических алгоритмов. Конечно, и такая проверка не является непогрешимой, так как и работа с «избытками» подвержена ошибкам, но такая ситуация маловероятна.

Проценты.

Процентом называется дробь, у которой знаменатель равен 100; проценты можно записать тремя способами: как обыкновенную дробь, как десятичную дробь или с помощью специального обозначения процентов %. Например, 7 процентов можно записать как 7/100, как 0,07 или как 7%.

Примером самого распространенного типа задач на проценты может служить следующая: «Найти 17% от 82». Чтобы решить эту задачу, нужно вычислить произведение 0,17ґ82 = 13,94. В произведениях такого рода 0,17 называется ставкой, 82 – базой, а 13,94 – долей, выраженной в процентах. Три упомянутые величины связаны между собой соотношением

Ставка ґ база = доля в процентах.

Если любые две величины известны, третью можно определить из этого соотношения. Соответственно мы получаем три типа задач «на проценты».

Пример 1 . Число учащихся, записавшихся в данную школу, выросло с 351 до 396 человек. На сколько процентов возросло это число?

Прирост составил 396 – 351 = 45 человек. Записывая дробь 45/351 в процентах, получаем 45/351 = 0,128 = 12,8%.

Пример 2 . Объявление в магазине во время распродажи гласит «Скидка на все товары 25%». Какова цена во время распродажи на товар, который обычно продается за 3,60 доллара?

Снижение цены 3,60 доллара на 25% означает снижение на 0,25ґ3,60 = 0,90 доллара; следовательно, цена на товар во время распродажи составит 3,60 – 0,90 = 2,70 доллара.

Пример 3 . Деньги, положенные в банк под 5% годовых, принесли прибыль в 40 долларов за год. Какая сумма была помещена в банк?

Так как 5% от суммы составляет 40 долларов, т.е. 5/100 ґ сумма = 40 долларов, или 1/100 ґ сумма = 8 долларов, вся сумма составляет 800 долларов.

Арифметика приближенных чисел.

Многие числа, используемые в вычислениях, возникают либо из измерений, либо из оценок и поэтому могут рассматриваться лишь как приближенные. Очевидно, что результатом вычислений, производимых с приближенными числами, может быть только приближенное число. Например, предположим, что измерения поверхности прилавка дали следующие результаты (с округлением до ближайшей десятой метра): ширина 1,2 м, длина 3,1 м; можно было бы сказать, что площадь прилавка составляет 1,2ґ3,1 = 3,72 м 2 . Однако в действительности информация далеко не столь определенна. Так как величина 1,2 м указывает лишь на то, что результат измерения ширины заключен между 1,15 и 1,25 м, а 3,1 – на то, что результат измерения длины заключен между 3,05 и 3,15 м, о площади прилавка можно лишь сказать, что она должна быть больше, чем 1,15ґ3,05 = 3,5075, но меньше, чем 1,25ґ3,15 = 3,9375. Следовательно, единственный разумный ответ на вопрос о площади прилавка состоит в утверждении, что она приблизительно равна 3,7 м 2 .

Рассмотрим далее проблему сложения результатов приближенных измерений 3,73 м, 52,1 м и 0,282 м. Простая сумма равна 56,112 м. Но, как и в предыдущей задаче, все, что можно сказать с уверенностью, так это то, что истинная сумма должна быть больше, чем 3,725 + 52,05 + 0,2815 = 56,0565 м и меньше, чем 3,735 + 52,15 + 0,2825 = 56,1765 м. Таким образом, единственный разумный ответ на вопрос сводится к утверждению, что сумма приближенно равна 56,1 м.

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

Если же первая отбрасываемая цифра в точности равна пяти, то последняя сохраняемая цифра увеличивается на единицу, если она нечетная, и остается без изменений, если она четная. Например, при округлении до сотых числа 3,14159;17,7682; 28,999; 0,00234; 7,235 и 7,325 переходят в числа 3,14; 17,77; 29,00; 0,00; 7,24 и 7,32.

Другой способ округления связан с понятием значащих цифр и используется при машинной записи числа. Значащими цифрами приближенного числа называются цифры в его десятичной записи по порядку слева направо, начиная с первой отличной от нуля цифры и кончая той цифрой, которая стоит на месте десятичного знака, соответствующего ошибке. Например, значащими цифрами приближенного числа 12,1 являются цифры 1, 2, 1; приближенного числа 0,072 – цифры 7, 2; приближенного числа 82000, записанного с точностью до сотен, – 8, 2, 0.

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

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

Возвращаясь к ранее рассмотренным задачам, получаем:

1,2ґ3,1 = 3,72 м 2 » 3,7 м 2

3,73 + 52,1 + 0,28 = 56,11 м 2 » 56,1 м,

где знак » означает «приближенно равно».

В некоторых учебниках арифметики приводятся алгоритмы для работы с приближенными числами, позволяющие избегать при вычислениях лишних знаков. Кроме того, в них используется т.н. запись приближенных чисел, т.е. любое число представляется в виде (число, заключенное в интервале от 1 до 10) ґ (степень числа 10), где в первом множителе содержатся только значащие цифры числа. Например, 82000 км, округленные до ближайшего числа сотен км, запишется как 8,20ґ10 4 км, а 0,00702 см – как 7,02ґ10 –3 см.

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

Логарифмы.

К началу 17 в. сложность прикладных вычислительных задач возросла настолько, что справиться с ними «вручную» не представлялось возможным из-за слишком больших затрат труда и времени. К счастью, вовремя изобретенные Дж.Непером в начале 17 в. логарифмы позволили справиться с возникшей было проблемой. Так как теория и приложения логарифмов подробно изложены в специальной статье ЛОГАРИФМ , мы ограничимся лишь самыми необходимыми сведениями.

Можно показать, что если n – положительное действительное число, то существует единственное положительное действительное число x , такое, что 10 x = n . Число x называется (обычным или десятичным) логарифмом числа n ; условно это записывается так: x = log n . Таким образом, логарифм – это показатель степени, и из законов действий с показателями следует, что

Именно этими свойствами логарифмов объясняется их широкое использование в арифметике. Первое и второе свойства позволяют свести любую задачу на умножение и деление к более простой задаче на сложение и вычитание. Третье и четвертое свойства дают возможность свести возведение в степень и извлечение корня к гораздо более простым действием: умножению и делению.

Для удобства использования логарифмов были составлены их таблицы. Для составления таблицы десятичных логарифмов достаточно включить в них только логарифмы чисел от 1 до 10. Например, так как 247,6 = 10 2 ґ2,476, имеем: log247,6 = log10 2 + log2,476 = 2 + log2,476, а так как 0,02476 = 10 –2 ґ2,476, то log0,02476 = log10 –2 + log2,476 = –2 + log2,476. Заметим, что десятичный логарифм числа, заключенного в интервале от 1 до 10, лежит в интервале от 0 до 1 и может быть записан в виде десятичной дроби. Отсюда следует, что десятичный логарифм любого числа есть сумма целого числа, называемого характеристикой логарифма, и десятичной дроби, называемой мантиссой логарифма. Характеристику логарифма любого числа можно найти «в уме»; мантиссу же следует находить по таблицам логарифмов. Например, из таблиц мы находим, что log2,476 = 0,39375, откуда log247,63 = 2,39375. Если характеристика логарифма отрицательна (когда число меньше единицы), то ее удобно представить в виде разности двух положительных целых чисел, например, log0,02476 = –2 + 0,39375 = 8,39375 – 10. Следующие примеры поясняют этот прием.

Литература:

История математики с древнейших времен до начала XIX в ., тт. 1–3. М., 1970–1972.
Серр Ж.-П. Курс арифметики . М., 1972
Нечаев В.И. Числовые системы . М., 1975
Даан-Дальмедико А., Пейффер Ж. Пути и лабиринты. Очерки по истории математики . М., 1986
Энглер Э. Математика элементарной математики . М., 1987



Рассмотрим этот алгоритм на примере. Найдем

1-й шаг. Число под корнем разбиваем на грани по две цифры (справа налево):

2-й шаг. Извлекаем квадратный корень из первой грани, т. е. из числа 65, получаем число 8. Под первой гранью пишем квадрат числа 8 и вычитаем. К остатку приписываем вторую грань (59):

(число 159 - первый остаток).

3-й шаг. Удваиваем найденный корень и пишем результат слева:

4-й шаг. Отделяем в остатке (159) одну цифру справа, слева получаем число десятков (оно равно 15). Затем делим 15 на удвоенную первую цифру корня, т. е. на 16, так как 15 на 16 не делится, то в частном получается нуль, который записываем как вторую цифру корня. Итак, в частном получили число 80, которое опять удваиваем, и сносим следующую грань

(число 15 901 - второй остаток).

5-й шаг. Отделяем во втором остатке одну цифру справа и полученное число 1590 делим на 160. Результат (цифру 9) записываем как третью цифру корня и приписываем к числу 160. Полученное число 1609 умножаем на 9 и находим следующий остаток (1420):

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

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

ДИДАКТИЧЕСКИЙ МАТЕРИАЛ

1. Извлеките квадратный корень из числа: а) 32; б) 32,45; в) 249,5; г) 0,9511.

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

Итак, сначала на примере рассказываю, “как работает система”, а потом объясняю, почему она на самом деле работает.

Возьмем число (число взято “с потолка”, только что в голову пришло).

1. Разбиваем его цифры на пары: те, что стоят слева от десятичной запятой, группируем по две справа налево, а те, что правее – по две слева направо. Получаем .

2. Извлекаем квадратный корень из первой группы цифр слева — в нашем случае это (ясно, что точно корень может не извлекаться, берем число, квадрат которого максимально близок к нашему числу, образованному первой группой цифр, но не превосходит его). В нашем случае это будет число . Записываем в ответ — это старшая цифра корня.

3. Возводим число, которое стоит уже в ответе — это — в квадрат и вычитаем из первой слева группы цифр — из числа . В нашем случае остается .

4. Приписываем справа следующую группу из двух цифр: . Число , которое уже стоит в ответе, умножаем на , получаем .

5. Теперь следите внимательно. Нам нужно к числу справа приписать одну цифру , и число умножить на , то есть на ту же самую приписанную цифру. Результат должен быть как можно ближе к , но опять-таки не больше этого числа. В нашем случае это будет цифра , ее записываем в ответ рядом с , справа. Это следующая цифра в десятичной записи нашего квадратного корня.

6. Из вычитаем произведение , получаем .

7. Далее повторяем знакомые операции: приписываем к справа следующую группу цифр , умножаем на , к полученному числу > приписываем справа одну цифру, такую, чтобы при умножении на нее получилось число, меньшее , но наиболее близкое к нему –– это цифра –– следующая цифра в десятичной записи корня.

Вычисления запишутся следующим образом:

А теперь обещанное объяснение. Алгоритм основан на формуле

Комментариев: 51

1. 2 Антон:

   Слишком сумбурно и запутано. Разложите всё по пунктам и пронумеруйте их. Плюс: объясните откуда в каждом действии мы подставляем нужные значения. Никогда раньше не вычислял корень в столбик – разобрался с трудом.

2. 5 Юлия:

3. 6 :

   Юлия, 23 на данный момент записано справа, это две первые (слева) уже полученные цифры корня, стоящие в ответе. Умножаем на 2 согласно алгоритму. Повторяем действия, описанные в пункте 4.

4. 7 zzz:

   ошибка в “6. Из 167 вычитаем произведение 43 * 3 = 123 (129 нада), получаем 38.”
   непонятно как после запятой получилось 08…

5. 9 Федотов Александр:

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

6. 10 :

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

7. 12 Сергей Валентинович:

   Уважаемая Елизавета Александровна! Мной в конце 70-х разработана схема автоматического (т.е. не подбором) вычисления квадр. корня на арифмометре “Феликс”. Если заинтересуетесь, могу выслать описание.

8. 14 Vlad aus Engelsstadt:

   (((Извлечение квадратного корня в столбик)))
   Алгоритм упрощается, если использовать 2-ную систему счисления, которую изучают в информатике, но полезно и в математике. А.Н. Колмогоров в популярных лекциях для школьников приводил этот алгоритм. Его статью можно найти в “Чебышёвском сборнике” (Математический журнал, ищите ссылку на него в интернете)
   К случаю сказать:
   Г.Лейбниц в свое время носился с идеей о переходе от 10-ной системы счисления к двоичной из-за ее простоты и доступности для начинающих (младших школьников). Но устоявшиеся традиции ломать это все равно что лбом ломать крепостные ворота: можно, но бесполезно. Вот и получается как по наиболее цитируемому в былые времена бородатому философу: традиции всех мертвых поколений подавляют сознание живых.

   До следующих встреч.

9. 15 Vlad aus Engelsstadt:

   ))Сергей Валентинович, да, мне интересно…((

   Бьюсь об заклад, что это вариация под “Феликс” Вавилонского метода извлечения коня квадратного методом последовательных приближений. Этот алгоритм был перекрыт методом Ньютона (метод касательных)

   Интересно, не ошибся ли я в прогнозе?

10. 18 :

    2Vlad aus Engelsstadt

    Да, алгоритм в двоичной системе должен быть проще, это довольно очевидно.

    О методе Ньютона. Может, оно и так, но все равно интересно

11. 20 Кирилл:

    Спасибо большое. А алгоритма так и нету, неизвестно откуда он взялся, но результат правильный получается. СПАСИБО БОЛЬШОЕ! Долго искал это)

12. 21 Александр:

    А каким образом пойдёт извлечение корня из числа, где вторая слева-направо группа весьма мала? к примеру, любимое всеми число 4 398 046 511 104 . после первого вычитания не получается продолжить всё по алгоритму. Объясните пожалуйста.

13. 22 Алексей:

    Да, знаю этот способ. Я, помню, вычитал его в книге “Алгебра” какого-то старого издания. Тогда еще по аналогии сам вывел, как так же в столбик извлекать кубический корень. Но там уже сложнее: каждая цифра определяется уже не в одно (как для квадратного), а в два вычитания, да еще там каждый раз надо перемножать длинные числа.

14. 23 Артем:

    В примере извлечения квадратного корня в столбик из 56789,321 имеются опечатки. Группа цифр 32 приписана дважды к числам 145 и 243, в числе 2388025 вторую 8 необходимо заменить на 3. Тогда последнее вычитание следует записать так: 2431000 – 2383025 = 47975.
    Дополнительно, при делении остатка на увеличенное в два раза значение ответа (без учета запятой), получим добавочное количество значащих цифр (47975/(2*238305) = 0.100658819…), которые следует дописать к ответу (√56789,321 = 238,305… = 238,305100659).

15. 24 Сергей:

    По всей видимости алгоритм пришел из книги Исаака Ньютона “Всеобщая арифметика или книга о арифметических синтезе и анализе”. Вот выдержка из неё:

    ОБ ИЗВЛЕЧЕНИИ КОРНЕЙ

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

16. 25 Сергей:

    Поправьте ещё название книги “Всеобщая арифметика или книга оБ арифметических синтезе и анализе”

17. 26 Александр:

    Спасибо за интересный материал. Но мне этот метод представляется несколько более сложным, чем нужно, например, школьнику. Я применяю более просто метод, основанный на разложении квадратичной функции с помощью первых двух производных. Формула его такая:
    sqrt(x)= A1+A2-A3, где
    А1 – целое число, квадрат которого ближе всего к х;
    А2 – дробь, в числителе х-А1, в знаменателе 2*А1.
    Для большинства чисел, встречающихся в школьном курсе, этого достаточно, чтобы получить результат с точностью до сотых.
    Если нужен более точный результат, берем
    А3 – дробь, в числителе А2 в квадрате, в знаменателе 2*А1+1.
    Конечно, для применения нужна таблица квадратов целых чисел, но это в школе не проблема. Запомнить эту формулу достаточно просто.
    Меня, правда, смущает, что А3 я получил опытным путем в результате экспериментов с электронной таблицей и не вполне понимаю, почему этот член имеет такой вид. Может, подскажете?

18. 27 Александр:

    Да, я тоже рассматривал эти соображения, но дьявол кроется в деталях. Вы пишете:
    “поскольку a2 и b отличаются уже довольно мало”. Вопрос именно стоит, насколько мало.
    Эта формула хорошо работает на числах второго десятка и гораздо хуже (не до сотых, только до десятых) на числах первого десятка. Почему так происходит уже трудно понять без привлечения производных.

19. 28 Александр:

    Я уточню, в чем я вижу преимущество предложенной мной формулы. Она не требует не вполне естественного разбиения чисел на пары цифр, которое, как показывает опыт, часто выполняется с ошибками. Смысл ее очевиден, а для человека, знакомого с анализом, тривиален. Хорошо работает на числах от 100 до 1000, наиболее часто встречающихся в школе.

20. 29 Александр:

    Кстати, я немного покопался и нашел точное выражение для А3 в моей формуле:
    А3= А22 /2(A1+A2)

21. 30 vasil stryzhak:

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

22. 31 Александр:

    для 30 vasil stryzhak
    Я ни о чем не умолчал. Таблица квадратов предполагается до 1000. В мое время в школе ее просто заучивали наизусть и она была во всех учебниках математики. Я в явном виде назвал этот интервал.
    Что до вычислительной техники, то она не применяется, в основном, на уроках математики, если только не идет специально тема применения калькулятора. Калькуляторы сейчас встроены в устройства, запрещенные к применению на ЕГЭ.

23. 32 vasil stryzhak:

    Александр, спасибо за разъяснение!Я считал,что для предлагаемого метода теоретически необходимо помнить или пользоваться таблицей квадратов всех двузначных чисел.Тогда для подкоренных чисел не входящих в интервал от 100 до 10000 можно использовать прием их увеличения или уменьшения на необходимое количество порядков переносом запятой.

24. 33 vasil stryzhak:

25. 39 АЛЕКСАНДР:

    МОЯ ПЕРВАЯ ПРОГРАММА НА ЯЗЫКЕ “ЯМБ” НА СОВЕТСКОЙ МАШИНЕ “ИСКРА 555″ БЫЛА НАПИСАНА ДЛЯ ИЗВЛЕЧЕНИЯ КВАДРАТНОГО КОРНЯ ИЗ ЧИСЛА ПО АЛГОРИТМУ ИЗВЛЕЧЕНИЯ В СТОЛБИК! а сейчас забыл как извлекать в ручную!

В предисловии к своему первому изданию “В царстве смекалки” (1908 год) Е. И. Игнатьев пишет: “... умственную самодеятельность, сообразительность и “смекалку” нельзя ни “вдолбить”, ни “вложить” ни в чью голову. Результаты надёжны лишь тогда, когда введение в область математических знаний совершается в лёгкой и приятной форме, на предметах и примерах обыденной и повседневной обстановки, подобранных с надлежащим остроумием и занимательностью”.

В предисловии к изданию 1911 г “Роль памяти в математике” Е.И. Игнатьев пишет “… в математике следует помнить не формулы, а процесс мышления”.

Для извлечения квадратного корня существуют таблицы квадратов для двухзначных чисел, можно разложить число на простые множители и извлечь квадратный корень из произведения. Таблицы квадратов бывает недостаточно, извлечение корня разложением на множители - трудоёмкая задача, которая тоже не всегда приводит к желаемому результату. Попробуйте извлечь квадратный корень из числа 209764? Разложение на простые множители дает произведение 2*2*52441. Методом проб и ошибок, подбором – это, конечно, можно сделать, если быть уверенным в том, что это целое число. Способ, который я хочу предложить, позволяет извлечь квадратный корень в любом случае.

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

Основой этого способа, является состав числа =.

=&, т.е. & 2 =596334.

1. Разбиваем число (5963364) на пары справа налево (5`96`33`64)

2. Извлекаем квадратный корень из первой слева группы ( - число 2). Так мы получаем первую цифру числа &.

3. Находим квадрат первой цифры (2 2 =4).

4. Находим разность первой группы и квадрата первой цифры (5-4=1).

5.Сносим следующие две цифры (получили число 196).

6. Удваиваем первую, найденную нами цифру, записываем слева за чертой (2*2=4).

7.Теперь необходимо найти вторую цифру числа &: удвоенная первая цифра, найденная нами, становится цифрой десятков числа, при умножении которого на число единиц, необходимо получить число меньшее 196 (это цифра 4, 44*4=176). 4 - вторая цифра числа &.

8. Находим разность (196-176=20).

9. Сносим следующую группу (получаем число 2033).

10. Удваиваем число 24, получаем 48.

11.48 десятков в числе, при умножении которого на число единиц, мы должны получить число меньшее 2033 (484*4=1936). Найденная нами цифра единиц (4) и есть третья цифра числа &.

Доказательство приведено мной для случаев:

1. Извлечение квадратного корня из трехзначного числа;

2. Извлечение квадратного корня из четырехзначного числа.

Приближенные методы извлечения квадратного корня (без использования калькулятора) .

1.Древние вавилоняне пользовались следующим способом нахождения приближенного значения квадратного корня их числа х. Число х они представляли в виде суммы а 2 +b, где а 2 ближайший к числу х точный квадрат натурального числа а (а 2 ?х), и пользовались формулой . (1)

Извлечем с помощью формулы (1) корень квадратный, например из числа 28:

Результат извлечения корня из 28 с помощью МК 5,2915026.

Как видим способ вавилонян дает хорошее приближение к точному значению корня.

2. Исаак Ньютон разработал метод извлечения квадратного корня, который восходил еще к Герону Александрийскому (около 100 г. н.э.). Метод этот (известный как метод Ньютона) заключается в следующем.

Пусть а 1 - первое приближение числа (в качестве а 1 можно брать значения квадратного корня из натурального числа - точного квадрата, не превосходящего х) .

Следующее, более точное приближение а 2 числа найдется по формуле .