Теория чисел

Виноградов И.М. «Основы теории чисел»

Теория чисел 

Делимость

1. Целые числа: натуральные числа, 0 и отрицательные. Разница между соседними числами 1. 
2. a + b, a - b, a * b целые.
3. Если a = b * q (при условии b q целые) обозначается b \ a 
   1. a кратно числу b
   2. b делитель числа a
4. Если b \ m и m \ a то b \ a
5. Если в равенстве вида  

   a+b+...+m = n+o+...+z

    известно для всех членов, кроме одного, что они кратны x, то этот один тоже кратен x. 
6. a представляется единственным способом в виде 

   a = bq+r
   где 0<=r<b

7. НОД a, b ... z обозначается (a, b, ... z)
8. Если (a, b, ... z) = 1 то эти числа взаимно простые
9. Если каждое из чисел (a, b, ... z) взаимно просто с каждым другим, то эти числа попарно простые
10. Если a кратно b, то совокупность общих делителей чисел a и b совпадает с совокупность делителей b 

    a = q*b
    (a,b) = b

11. Поиск НОД - алгоритм Евклида. a, b положительны и a > b. НОД равен последнему не равному 0 остатку.
12. m любое положительное целое. (am, bm) = (a, b)m
13. Если (a,b) = 1 то (ac, b) = (c,b)
14. Если каждое a1 a2 ... an взаимно просто с b1 b2 ... bn то произведение a1 * a2 * ... * an взаимно просто с b1 * b2 * ... * bn
15. Совокупность общих кратных двух чисел совпадает с совокупностью кратных их общего наименьшего кратного
16. Общее наименьшее кратное равно их произведению деленному на НОД
17. Числа либо простые, либо составные. Составные = произведение простых в степени.
18. Всякое a либо взаимно просто с простым p, либо делится на p
19. Разложение составного числа на простые сомножители единственно. Это называется каноническое разложение.
20. Пусть A - каноническое разложение = p[i] ^ a[i] тогда все делители - числа вида p[i] ^ b[i] где 0 <= b[i] <= a[i] 
21. Вещественные числа - разложения, рациональные/иррациональные - стр. 20

Важнейшие функции

1. x - вещественное число. [x] - максимальное целое число, не превосходящее x. {x} дробная часть = x - [x]
2. Функция мультипликативная, если
   1. определена для всех целых положительных и не равна 0 как минимум при одном. 
   2. Для любых положительных взаимно простых a b выполняется x[ab] = x[a]x[b]
3. Для мультипликативной функции x, x[1] = 1
4. Произведение мультипликативных функций также мультипликативная функция.

Сравнение

Сравнимость чисел a и b по модулю m равносильна:

• Возможности представить a = b + mt где t целое
• Делимости a-b на m

Дополнительные свойства:

• Сравнение можно почленно складывать.
• Можно добавлять отрицательное значение в обе части равенства.
• Можно почленно перемножать
• Можно возвести в степень
• Обе части можно делить на делитель, взаимно простой с модулем. Очень важное правило.
• Можно делить обе части одновременно a,b,m То есть a=2x b=2y m=2z Следовательно, мы можем поделить все на 2.
  x = y mod z
• Если a=b по нескольким модулям, то и по их НОК
• Если m не целое, то a=b актуально для любого делителя m