uzluga.ru
добавить свой файл
Гимназия 1543, 8-В класс Листик 9, 13 февраля 2010.

Целые числа 2.

При решении первых 7 задач термин простое число запрещен.

Определение. Наибольшим общим делителем двух целых чисел a и b называется наибольшее натуральное число, на которое они оба делятся. Обозначение: НОД(a,b) или (a,b). Числа, НОД которых равен единице, называются взаимно простыми.

  1. Докажите, что а) НОД(a,b)=b тогда и только тогда, когда ;

б) НОД(a-b,b)=НОД(a,b).

в) Пусть a при делении на b дает остаток r. Докажите, что НОД(a,b)=НОД(b,r).

    Алгоритм Евклида: для того, чтобы найти НОД двух чисел a и b, нужно выполнить последовательно несколько делений с остатком:

    a = b q1+r1

    b = r1q2+r2

    r1 = r2q3+r3

    r2 = r3q4+r4

    …………

    rn–2= rn–1qn+rn

    rn–1= rn qn+1

    На каждом шаге предыдущий делитель делится с остатком на предыдущий остаток. Так продолжается до тех пор, пока на каком-то шаге остаток не станет равен 0. Последний ненулевой остаток rn равен НОД(a,b).

  1. Докажите, что rn=НОД(a,b).

  2. Найдите а) НОД(1543,2010) б) НОД(-144,-233) в)  г) 

  3. Коля берёт прямоугольный бумажный лист mn см, отрезает от него квадрат со стороной, равной меньшей стороне прямоугольника, и кидает его на пол. От оставшегося прямоугольника он снова отрезает квадрат, кидает на пол и так далее, до тех пор, пока это возможно. Что же останется в руках у Коли, когда он закончит свою деятельность и приступит к уборке мусора?

  4. а) Докажите, что для любого натурального a дробь несократима.

б) А на сколько может быть сокращена дробь ?

  1. (Линейное представление НОД) Докажите, что для любых a, b, не равных нулю одновременно, существуют такие целые x,y, что НОД(a,b)=ax+by.

Указание: докажите, что в виде ax+by представляются числа r1, r2, …,rn.

  1. а) Найдите x,y (см задачу 6) для чисел 32 и 25.

б) Даны углы 32 и 25. Построить угол 1.

Определение. Число p>1 называется простым, если оно делится только на и . Остальные натуральные числа, кроме единицы, называются составными.

  1. а)*Докажите, что если p простое число, , то либо либо .

б) Существуют ли составные числа p с таким свойством?

  1. (Основная теорема арифметики) а) Докажите, что любое натуральное число n можно представить в виде произведения простых чисел. Т.е.

б) Докажите, что это представление единственно с точностью до перестановки сомножителей. (Указание: используйте задачу 8а)

  1. Сколько различных натуральных делителей у числа а) б) в) , где pi – различные простые числа.

  2. Найдите сумму натуральных делителей числа а) б) в) , где piразличные простые числа.

  3. У каких натуральных чисел количество делителей нечетно?

  4. а) Пусть p1, p2,…,pk простые числа. Докажите, что число p1,p2pk+1 имеет простой делитель, отличный от p1, p2,…,pk.

б) Докажите, что простых чисел бесконечно много.

  1. а) Докажите, что найдутся 100 подряд идущих составных чисел. (Указание: рассмотрите числа вида 101!+2, 101!+3,…,101!+101)

б) Докажите, что найдутся 100 подряд идущих чисел, среди которых ровно одно простое.

  1. Докажите, что если p>3 ­простое число, то делится на 24.

  2. Найдите все числа p, для которых p, p+2, p+4 – простые.

Определение. Наименьшим общим кратным двух натуральных чисел a и b называется наименьшее натуральное число, делящееся на каждое из них. Обозначение: НОК(a,b).

  1. а) Пусть , . Найдите НОД(m,n) и НОК(m,n).

б) Докажите, что mn= НОД(m,n) НОК(m,n)

Еще задачи.

  1. (Другое решение задачи 6, при решении задачами 6-17 пользоваться нельзя) Для данных a и b обозначим через I – множество чисел представимых в виде ax+by, где x и y   целые. а) Докажите, что если m и n принадлежат I, то m+n, m-n, mk тоже принадлежат I. (k – любое целое)

б) Пусть d наименьшее натуральное число в I. Докажите, что для любого m из I, .

в) Докажите a и b делятся на d.

г) Докажите, что d делится на НОД(a,b).

д) Докажите, что НОД(a,b) представляется в виде ax+by, где x и y – целые.

  1. Докажите, что простых чисел вида 4k+3 бесконечно много.

  2. На доске написаны два различных натуральных числа a и b . Меньшее из них стирают, и вместо него пишут число (которое может уже оказаться нецелым). С полученной парой чисел делают ту же операцию и т.д. Докажите, что в некоторый момент на доске окажутся два равных натуральных числа.

  3. Шайка разбойников отобрала у купца мешок с монетами. Каждая монета стоит целое число грошей. Оказалось, что какую монету не отложи, оставшиеся монеты можно поделить между разбойниками так, что каждый получит одинаковую сумму. Докажите, что число монет без одной делится на число разбойников в шайке.

  4. а) Докажите, что показатель степени простого числа p в разложении n! на простые множители (иногда говорят p-показатель) равен .

б) Найдите формулу для p-показателя числа . Докажите, что он неотрицателен.

в) Выведите из формулы пункта б), что кратно p, при .