Делимость и алгоритм Евклида

Делители и делимость. Для данных целых чисел a и b говорят, что a делит b (или b делится на a), и используют обозначение a|b, если существует такое целое число d, что b = a*d. В этом случае a называют делителем b. Любое целое число b > 1 имеет, по крайней мере, два положительных делителя: 1 и b. Под собственным делителем b подразумевают любой положительный делитель, не равный b, а под нетривиальным делителем b — любой положительный делитель, не равный 1 или b. Простым числом, по определению, является целое число, большее 1, которое не имеет положительных делителей, отличных от 1 и самого себя; число называется составным, если оно имеет, по крайней мере, один нетривиальный делитель. Следующие свойства делимости выводятся непосредственно из определений:

• 1. Если a|b и с — любое целое число, то а|(b*c)
• 2. Если a|b и b|c, то a|c
• 3. Если a|b и a|c, то a|(b ± с)
• 4. Если простое число p делит a*b, то p|a или p|b.
• 5. Если m|a и n|a и если m и n не имеют общих делителей, больших 1, то m*n|a.

Наибольший общий делитель. Наибольшим общим делителем двух данных целых чисел a и b (обозначаемым НОД (a, b) или просто (a, b)), не равных одновременно нулю, называется наибольшее целое число d, делящее и a, и b. Приведенное выше определение эквивалентно следующему: НОД (a, b) — это единственное положительное число, которое делит a и b и делится на любой другой их общий делитель.

Если имеются разложения на простые множители двух чисел a и b, следует взять все простые числа, входящие в оба разложения, и каждое возвести в степень, равную минимуму из двух соответствующих показателей. Наименьшее общее кратное чисел a и b обозначается НОК (а, b) и по определению является наименьшим целым положительным числом, делящимся как на a, так и на b. Имея разложение на простые множители чисел a и b, можно получить НОК (a, b), взяв все простые числа, входящие хотя бы в одно из разложений, и каждое возвести в степень, равную максимуму из двух показателей. НОК (a, b) = |a*b| / НОД (a, b).

Алгоритм Евклида. При работе с большими числами часто случается, что их разложение на простые множители неизвестно. В частности, важным направлением исследований в теории чисел является отыскание быстрых методов разложения больших чисел на простые множители. К счастью, существует сравнительно быстрый способ нахождения НОД (a, b) даже в том случае, когда неизвестны простые делители a или b. Он называется алгоритмом Евклида. Алгоритм Евклида работает следующим образом. Чтобы найти НОД (a, b), где a > b, сначала делят a на b и записывают частное q-₁ и остаток r₁: a = q₁ * b + r₁. Затем производят второе деление, в котором b играет роль a, а r₁ — роль b: b = q₂ * r₁ + r₂. Затем делят r₁ на r₂. Деление продолжают, каждый раз деля предпоследний остаток на последний, получая новые частное и остаток. Когда в конце концов получается остаток, который является делителем предыдущего остатка, то этот последний ненулевой остаток и есть наибольший общий делитель чисел a и b.