Def === Число называется ПРОСТЫМ если оно имеет только 2 делителя единицу и само себя. (1 не считается простым числом). Решето Эратосфена: 2 3 X 5 X 7 X X X 11 X 13 X X X 17 X 19 X X X 23 X X X X X 29 X 31 X X X X X 37 X X X 41 ... Простые числа
m \ n = значит m делит n наибольший общий делитель: hcf highest common factor (UK) gcd greatest common divisor (US) НОД(m,n) = MAX(k | k\m и k\n ) Алгоритм Евклида: НОД(0, n) = n НОД(m, n) = НОД(n mod m, m) при m > 0 наименьшее общее кратное: НОК(m,n) = MIN(k | k>0, m\k, n\k) НОД и НОК
Остаток от деления x mod y = x - y| x/y | +- -+ целая часть - округление к низу 5 mod 3 = 2 = 5 - 3 * ROUND_LOW(5/3) = 5 - 3*1 = 2 5 mod -3 = -1 = 5 - (-3) * ROUND_LOW(5/-3) = 5 - (-3)*(-2) = 5-6 = -1 -5 mod 3 = 1 = -5 - 3 * ROUND_LOW(-5/3) = -5 - (-3)*2 = 5+6 = 1 -5 mod -3 = -2 = -5 - (-3)*ROUND_LOW(-5/-3) = -5 - (-3)*1 = 5+3 = =-2 c (x mod y) = (cx) mod (cy) Остаток от деления
Zn множество Z = Цифры: {0,1,...,n-1} по модулю n все действия осуществляются по модулю n. Пример по модулю 6: +| 0 1 2 3 4 5 --+------------- 0| 0 1 2 3 4 5 1| 1 2 3 4 5 0 2| 2 3 4 5 0 1 3| 3 4 5 0 1 2 4| 4 5 0 1 2 3 5| 5 0 1 2 3 4 *| 0 1 2 3 4 5 --+------------- 0| 0 0 0 0 0 0 1| 0 1 2 3 4 5 2| 0 2 4 0 2 4 3| 0 3 0 3 0 3 4| 0 4 2 0 4 2 5| 0 5 4 3 2 1 Кольца вычетов
Пример по модулю 8 +| 0 1 2 3 4 5 6 7 --+----------------- 0| 0 1 2 3 4 5 6 7 1| 1 2 3 4 5 6 7 0 2| 2 3 4 5 6 7 0 1 3| 3 4 5 6 7 0 1 2 4| 4 5 6 7 0 1 2 3 5| 5 6 7 0 1 2 3 4 6| 6 7 0 1 2 3 4 5 7| 7 0 1 2 3 4 5 6 *| 0 1 2 3 4 5 6 7 --+----------------- 0| 0 0 0 0 0 0 0 0 1| 0 1 2 3 4 5 6 7 2| 0 2 4 6 0 2 4 6 3| 0 3 6 1 4 7 2 5 4| 0 4 0 4 0 4 0 4 5| 0 5 2 7 4 1 6 3 6| 0 6 4 2 0 6 4 2 7| 0 7 6 5 4 3 2 1
Законы арифметики в кольцах вычетов: Коммутативные: (w+x) mod n = (x+w) mod n (w*x) mod n = (x*w) mod n Ассоциативные: [(w+x)+y] mod n = [w + (x+y)] mod n [(w*x)*y] mod n = [w * (x*y)] mod n Дистрибутивный: [(w+x)*y] mod n = [(w*y)+(x*y)] mod n Тождества: (0+w) mod n = w mod n (1*w) mod n = w mod n Для любого w, существует такое z, что w+z = 0 mod n Если (a+b) = (a + c) mod n, то b = c mod n Если (a*b) = (a*c) mod n, то b = c mod n, только если a и n - взаимно простые числа. Пример: 6*3 = 18 = 2 mod 8 6*7 = 42 = 2 mod 8