Разложение числа на множители

Будем раскладывать скажем число 360 на множители простым способом:

Итак, смотрим на что делится 360, а делится оно на: 2, 3, 5, 9, 10. Из этих чисел выбираем, которое больше нравится (мну нравится 3, она же неофициальная "зю") и делим на него:

360 / 3 = 120

Повторяем ситуацию с числом 120, оно делится на 2, 3, 5. Возьмем теперь эдак 5:

120 / 5 = 24

Смотрим, делится на 2, 3 возьмем 3

24 / 3 = 8

Ну и остается три раза на 2 поделить восемь:

8 / 2 = 4
4 / 2 = 2
2 / 2 = 1

Теперь выписываем все, на что мы делили и получаем: 2, 2, 2, 3, 5, 3 и ежели это перемножить - то получим исходное число 360.

Спрашивается: вот к чему вообще оно надо это разложение?

Конечно же для того, что бы взломать Криптосистему RSA! Вон оно оказывается чему в школе учат. :) Правда тут для разложения используют "Функцию Эйлера", которую я вспомню позднее.

Ну и еще это все надо для того, что бы найти "Наибольший общий делитель"(НОД) и "Наименьшее общее кратное"(НОК)

НОД

Возьмем два числа 360 и 420, разложим их и будем высматривать нечто одинаковое:

360 = 2*2*2*3*3*5
420 = 2*2*3*5*7

Теперь это одинаковое просто перемножим:

2 * 2 * 3 * 5 = 60

Выходит наибольший общий делитель это число 60.

НОК

Чтобы найти НОК - так же разложим число 360 и 420, только на этот раз добавим одному из них недостающие члены:

360 = 2*2*2*3*3*5
420 = 2*2*3*5*7

НОК = 2*2*3*5*7*2*3 = 2520

Проверка:

360 * 420 = НОД(60) * НОК(2520)
151200 = 151200

Вот все и сошлось.

Признаки делимости целых чисел

Основная теорема арифметики:

Каждое натуральное число, кроме 1, может быть разложено на простые множители единственным образом.

Признаки делимости целых чисел:

• Число делится на 2, если его последняя цифра 0, 2, 4, 6, 8.
• Число делится на 3, если сумма его цифр делится на 3. (Ха, помню надо было написать часть кода, где нужно было найти массив чисел, делящихся на 3 без остатка. И естественно это простое правило не вспомнил)
• Число делится на 4, если число из двух последних цифр делится на 4. (аналогично)
  
• Число делится на 5, если его последняя цифра 0 или 5.
• Число делится на 6, если оно делится на 2 и на 3.
• Число делится на 7, если
  
• Число делится на 9, если сумма его цифр делится на 9.
• Число делится на 10, если последняя цифра числа 0.
  

Приступимс...

В общем-то этот блог надо было начать еще лет эдак 6-7 назад, но увы, не начал. Теперь придется все наверстывать и вспоминать. И это, на самом деле, очень хорошо :)

Итак самые примитивные примитивы:

N - Множество натуральных чисел: 1, 2, 3, 4, 5, ... ∞.
Бывают простыми - с делителем, равным единице (1, 2, 3, 5, 7, 11, 13, 17, ... ∞)
И составными - с делителем, отличным от единицы (4, 6, 8, 9, 10, ... ∞)

Z - Множество Целых чисел: (-∞ ... , -3, -2, -1, 0, 1, 2, 3 ... ∞)

Z0 - Множество положительных целых чисел: 1, 2, 3, 4, ... ∞
Делятся на четные (2, 4, ... ∞) и нечетные (1, 3, ... ∞)

Q - Множество рациональных чисел - это:

• Целые числа (Z)
  
• Обыкновенная положительная или отрицательная дробь n/m, где n принадлежит множеству Z, а m множеству N
• Конечная или бесконечная периодическая, положительная или отрицательная десятичная дробь
  

I - Множество иррациональных чисел: бесконечная, десятичная непериодическая дробь (√2, π, ... )

R - Множество действительных чисел, рациональные, иррациональные, положительные
или отрицательные.

Так же имеет смысл представить вот такую схему:

Где видно, что каждый старший тип числа содержит в себе более младший.