13. Линейные диофантовы уравнения. Представление всех решений линейного диофантова уравнения.

Линейным диофантовым уравнением наз. уравнение вида b=a₁x₁+a₂x₂+...+a_nx_n (1), где все коэффициенты и свободный член – целые гауссовы числа.

Решение ищется в целых числах. Решением такого уравнения наз. упорядоченная совокупность чисел (к₁,к₂,...,к_n),k_i Z, n N, которое данное уравнение превращает в тождество a₁k₁+...+a_nk_n=b (2)

Критерий разрешимости: уравнение (1) разрешимо <=> НОД коэффициентов уравнения делит свободный член: b НОД(a₁,...,a_n)=d (3). Док-во: пусть к₁,к₂,...,к_n- решение, а раз решение, то подставляя в уравнение (1) и получаем (2).

a₁ d,..., a_n d => (a₁k₁+...+a_nk_n ) d <= дано: b d, b=db₁ д-ть, что есть решение

д-во: a₁с₁+...+a_nс_n=b, с_i Z a_n d =>(a₁k₁+...+a_nk_n ) d =>b d

Общее решение диофантового уравнения:

Общий метод решения: 1) a_i= 1 , X_i= b-a₁x₁+a₂x₂+...+a_nx_n , x₁,…,x_n - свободные неизвестные , ( k₁,…,k_n )- решения 2) a_i 1, =1 – наименьшее

Каждый коэффициент разделим на a₁ a_i=a₁q_i+r₁, o r_i

a₁x₁+( a₁q₂+r₂)x₂+…+( a₁q_n+r_n)x_n=b

a₁x₁+ a₁q₂ x₂+ r₂x₂+…+ a₁q_nx_n+r_nx_n=b

a₁(x₁+ q₂ x₂+ …+ q_nx_n) + r₂x₂+…+r_nx_n=b

x₁+ q₂ x₂+ …+ q_nx_n=y₁ a₁y₁ + r₂x₂+…+r_nx_n=0 (*)

док-во: пусть a₁k₁+...+a_nk_n=b- верное равенство. Тогда (к₁,к₂,...,к_n)-решение уравнения. k₁+ q₂ k₂+ …+ q_nk_n=y₁ подставим в (*): a₁(k₁+ q₂ k₂+ …+ q_nk_n) + +r₂k₂+…+r_nk_n= a₁k₁+( a₁q₂+r₂)k₂+…+ (a₁q_n+r_n)k_n=a₁k₁+a₂k₂+…+a_nk_n=b

2) обратимо: (любое решение (*) дает решение уравнения)

Пусть (m₁,m₂,...,m_n)-решение уравнения (*). Получаем a₁m₁+a₂m₂+…+a_nm_n=b

X₁+q₂m₂+…+q_nm_n=m₁, X₁= m₁– q₂m₂–…–q_nm_n

(m₁– q₂m₂–…–q_nm_n, m₂,…,m_n) – решение

a₁(m₁– q₂m₂–…–q_nm_n)+a₂m₂+…+a_nm_n=a₁m₁– a₁ q₂m₂–…–a₁

q_nm_n+a₂m₂+…+a_nm_n= a₁m₁+( a₁ q₂+r₂–a₁ q₂)m₂+…+(a₁ q_n+r_n– a₁q_n)m_n= =a₁m₁+r₂m₂+…+r_nm_n=b

14. Количество и сумма натуральных делителей. Мультипликативные числовые функции.

Опр. Пусть n N,число натуральных делителей числа n будем обозначать ,сумму натуральных делителей

Теорема1. Пусть натуральное число n>1 имеет представление n= ….. тогда

=

1)Каждый натуральный делитель числа n может быть записан в виде

….. где 0 .Чтобы найти количество делителей нужно посчитать количество всех возможных комбинаций s-упорядочных показателей степеней ( 0

……….

Так как

Всего значений

2)рассмотрим произведения

(1+ +…..+ ) (1+ +…..+ )…(1+ +…..+ )

0

Опр.Числовая функция f: наз. мультипликативной, если НОД(m,n)=1

f(m

Теорема2. Ф-ии

НОД(m,n)=1

m= …..

n= ….. ,

тогда ….. ….. )=

=( )( )=

аналогично и для

15. Целая часть числа и ее свойства.

[x] – эта ф-я задается на множ-ве R. Каждому действит числу ставится в соотв целое наибольшее число, не превыш. данное.

Пример: [3,2]=3, [-5,1]=-6, {x}=x-[x] n [x]<n+1, 0 {x}<1

Дробная часть{-5,1}=0,9

Теорема 1: Пусть R, d N. Тогда число положит чисел, не превосходящих равно .

Док-во: рассм. числа, кратные d. d,2d,…,sd, где sd <(s+1)d, s= . Ч.т.д.

Теорема 2:

Пусть р – простое нат число, n N, n 1, показатель, с кот данное простое р входит в каноническое разложение n! равно

Пример. С каким показателем число 3 входит в 40!