Практическое занятие №15

Наибольший общий делитель целых чисел и его свойства. Способы нахождения наибольшего общего делителя. Алгоритм Евклида. Линейное представление наибольшего общего делителя.

1. Доказать, что если а = bq +r, где а, b, r  0, то (а, b) = (b, r).

2. Доказать, что если (а₁, а₂) = d & (d₁, а₃) = d₂ &…& (d_n-2, a_n) = = d_n-1 => (a₁,a₂, a_n) = d_n-1.

3 Применяя алгоритм Евклида, найти НОД(а, b), если:

а) а = 6188, b = 4709.

б) а = 3164, b = 142.

в) а = 10248, b = 2142.

г) а = 4562, b = 356.

д) а = 1524, b = 240.

Практическое занятие №16

Взаимно простые числа и их свойства.

Наименьшее общее кратное целых чисел и его свойства. Способы нахождения наименьшего общего кратного.

1. Доказать, что если d = (a, b) => (а / d, b / d) = 1.

2. Доказать, что если ((аb) /с) & (а, с) = 1) => (b /с).

3. Доказать, что если (с /а) & (с /b) => (с /ab).

4. Доказать, что если ((а, с)=1) & (b, с) = 1) => (а  b, с) = 1.

5. Доказать, что [а, b] = ab/(а, b)

6. Доказать, что [a/k, b/k] = [а, b] / к, где к  0, kZ

7. Доказать, что если

( [а₁, а₂] = m₁) & ([m₁, а₃] = m₂) &... &([m_n-2, а_n] = m_n-1) => [а₁а₂...а_n]=m_n-1

8. Вычислить НОК [а, b], используя формулу:

[а, b] = ab/(а, b)

а) а = 84, b = 36

б) а = 72, b = 22

в) а = 124, b = 32

г) а = 244, b=18

9. С помощью решета Эратосфена выделить все простые числа от 2 до 100.

10. Выяснить, какие из чисел