Степени вхождения простых

Вспомним, что одно натуральное число делится на другое тогда и только тогда, когда для каждого простого множителя, входящего в разложение первого и второго чисел, степень вхождения в первое число не меньше степени вхождения во второе число.

Не умаляя общности, пусть тогда

1) Пусть НОД По определею НОД — это наибольший общий делитель и то есть и и делятся на и нет числа, большего, чем на которое так же делятся и и

Если степень вхождения в больше то не будет делиться на — противоречие.

Если степень вхождения в меньше и равна то где и взаимнопросты. Тогда и и делятся на а так же и и делятся на Из взаимнопростости и следует, что и и делятся на при этом — противоречие.

Получается, степень вхождения в равна

2) Пусть НОК По определею НОК — это наименьшее общее кратное и то есть делится и на и на и нет числа, меньшего, чем которое так же делится и на и на

Если степень вхождения в меньше то не будет делиться на — противоречие.

Если степень вхождения в больше и равна то где и взаимнопросты. Рассмотрим число Так как делится на и то в входят все простые числа, входящие в и кроме при этом их степень не меньше, чем в и Получатся, делится и на и на при этом — противоречие.

Получается, степень вхождения в равна