«Теория чисел» элективный курс по математике для 11 класса

Пояснительная записка

Теория чисел — это наука о целых числах. В основу этого раздела легло изучение свойств натуральных чисел, которое было начато еще математиками древности.

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

Знание данного раздела математике поможет вам в решении заданий С6 на ЕГЭ. Известно, что на ЕГЭ по математике многие школьники не приступают и даже не читают задание С6. «Все равно, мол, не решу». И очень напрасно!

Как правило, задача С6 состоит из двух или трех пунктов, среди которых есть совсем несложные. За всю задачу дается 4 первичных балла, по 1-2 балла за каждый пункт. По этому, сделав хотя бы часть задания, можно получить себе в копилку дополнительные первичные баллы. А они дадут прирост итогового результата по 100 бальной шкале.

Для решения задачи С6 необходим минимальный запас знаний. Это арифметика 6-го класса (все, что связано с делимостью) и сведения по прогрессиям из алгебры 9-го класса.

Почему же задача С6 считается (и, в общем-то, является) самой сложной на ЕГЭ по математике? Она нестандартна. Она требует так называемой математической культуры — умение грамотно строить рассуждения. А это умение у большинства школьников отсутствует начисто — ведь в школе, к сожалению, до развития математической культуры дело обычно не доходит.

Учиться культурно рассуждать можно и обязательно нужно. Задача С6 представляет для этого отличную возможность. Поэтому, чтобы как-то к этому подготовиться, я вам предлагаю элективный курс на 8 часов по теме «Теория чисел».

Содержание программы элективного курса.

Календарно — тематическое планирование.

1. Числовые множества.

В данном разделе мы определим числовые множества, необходимые для задачи С6.

Натуральные числа — это числа 1,2,3, … Натуральные числа мы используем для счета, а счет начинается с единицы. Поэтому — внимание: ноль не является натуральным числом!

Множество натуральных чисел обозначается N.

Целые числа — это числа 0, ±1, ±2, ±3 … Таким образом, целые числа - это ноль и «плюс — минус натуральные». Множество целых чисел обозначается Z.

Рациональные числа — это все возможные дроби m/n с целыми m и n (при этом конечно n ǂ 0). Любое целое число является в тоже время рациональным (например, 3 = 6/2). Однако число ½ не является целым.

Множество рациональных чисел обозначается Q.

Делимость.

Понятие делимости относится к целым числам. Начиная с этого момента все числа считаются целыми. Если в каком-то случае это окажется не так, мы сделаем специальную оговорку. Целые числа мы обозначаем a,b,c, …,k,l,m,n,...,x,y,z, то есть используем все строчные буквы латинского алфавита.

Определение. Число a делится на число b ǂ 0, если найдется число с такое, что а=bc. Если а делится на b, то число b называется делителем числа а.

Четность.

Число называется четным, если оно делится на 2. Число называется нечетным. Если оно не делится на 2.

Вот все четные числа: ±2, ±4, ±6, … Если а четно, то оно имеет вид а = 2n.

А вот все нечетные числа: ±1, ±3, ±5, … Если а нечетно, то оно имеет вид а = 2n + 1.

Следующие утверждения весьма очевидны и вы можете использовать их при решении задач С6.

- Сумма любого числа четных слагаемых четна.

- Сумма четного числа нечетных слагаемых четна. Сумма нечетного числа нечетных слагаемых нечетна.

- Пусть имеется произведение нескольких множителей. Если все множители нечетны, то произведение нечетно. Если хотя бы один множитель четный, то произведение четно.

Деление с остатком.

Любое число а можно разделить с остатком на любое число b ǂ 0. А именно, найдутся два числа q и r такие, что а = bq + r.

Число q называется частным, а число r — остатком от деления а на b. Если r = 0, то есть а = bq, то а делится на b.

Решение задач.

ЕГЭ 2011 год С6.

4. Найдутся ли хотя бы три десятизначных числа делящиеся на 11, в записи каждого из которых использованы все цифры от 0 до 9?

Решение:

Число делится на 11 тогда и только тогда, когда разность между суммами его цифр, стоящих на нечетных и на четных местах, делится на 11.

Запишем все цифры подряд: 9876543210. В написанном числе указанная разность сумм равна 5. Меняя местами, например, 5 и 8, мы одну сумму увеличивает на 3, а другую уменьшаем на 3. Значит, разность между суммами его цифр, стоящих на нечетных и на четных местах, становится равной 11. Меняя местами, например, 4 и 7, или 3 и 6, получаем требуемые примеры. Ответ: да, найдутся.

Примечание: В задаче не требуется нахождение всех чисел, обладающих указанным свойством.

3. Доказать, что произведение трех последовательных чисел делится на 6.

Решение: (n-1)*n*(n+1) – три последовательных числа. При делении на 6,остатки: 0;1;2;3;4;5;6. а) n=6g, если остаток 0. (6g-1)*6g*(6g+1):6 б) n=6g+1, если остаток 1. (6g+1-1)*(6g+1)*(6g+1+1):6 в) n=6g+2, если остаток 2. (6g+2-1)*(6g+2)*(6g+3):6 г) n=6g+3, д) n=6g+4, е) n=6g+5, аналогично.

2. Найдите наибольшее целое число, которое при делении на 11 дает в частном 10. Решение При делении на 11 остатки от 0 до 10. Число может быть 11*10+0; 11*10+1; 11*10+2;.... 11*10+10=120 Ответ: 120

1. Определить, делится ли число 87635064 на 11? Решение: (8+6+5+6) - (7+3+0+4) = 25-14= 11; 11:11=1 Ответ: да, делится.

2. Разложение на простые множители.

Всякое число, кроме единицы, которое делится только на единицу и само на себя, называется простым.

Число, которое делится не только на единицу и само на себя, но ещё и на другие числа, называется составным.

Любое натуральное число n, большее единицы, можно разложить в произведение простых чисел. Это разложение единственно, с точностью до порядка следования сомножителей.

Такое разложение называется — Каноническим разложением. Утверждение то существовании и единственности канонического разложения носит название основной теоремы арифметики.

Пусть n=p1^k1*p2^k2*...*ps^ks-каноническое разложение натурального числа n, тогда число r(n) натуральных делителей числа n, включая 1 и само число n, выражается формулой : r(n)=(k1+1)*(k2+1)*...*(ks+1)

Алгоритм Евклида – это алгоритм нахождения наибольшего общего делителя (НОД) пары целых чисел.

Наибольший общий делитель (НОД) – это число, которое делит без остатка два числа и делится само без остатка на любой другой делитель данных двух чисел. Проще говоря, это самое большое число, на которое можно без остатка разделить два числа, для которых ищется НОД.

Описание алгоритма нахождения НОД делением

Большее число делим на меньшее.

Если делится без остатка, то меньшее число и есть НОД (следует выйти из цикла).

Если есть остаток, то большее число заменяем на остаток от деления.

Переходим к пункту 1.

Пример:

Найти НОД для 30 и 18.

30/18 = 1 (остаток 12)

18/12 = 1 (остаток 6)

12/6 = 2 (остаток 0). Конец: НОД – это делитель. НОД (30, 18) = 6

Решение задач: 2. Найти НОД(645; 381) , используя алгоритм Евклида. Решение: Разделим 645 на 381. Мы получим: 645=381*1+264 , значит (645;381)=(381;117). 381= 264*1+117, значит (645;381)=(264;117). 264= 117*2+30 , значит (645;381)=(117;30). 117=30*3+27, значит (645;381)=(30;27). 30= 27*1+3, значит (645;381)=(27;3). 27=3*9+0, значит (27;3)=3 Ответ: НОД (645;381)=3 1. Запишите в каноническом виде разложение числа 1000000 и найдите число его делителей. Решение:1000000=2^6 * 5^6

r(n)=(6+1)*(6+1)=49 3. Найдите все натуральные числа, последняя десятичная цифра которых 0 и которые имеют ровно 15 различных делителей (включая 1 и само число). Решение: n=p1^k1*p2^k2*..., где p1,p2,...-простые числа, k1,k2,...- целые неотрицательные числа и количество делителей (k1+1)*(k2+1)*... Раз число n заканчивается на 0, то оно делится как минимум на два простых числа: 5 и 2 : n=2^k1*5^k2*..., k10,k20. Значит 15=3*5=5*3,отсюда 1) n=2^(3-1)*5^(5-1)=2500 , 2) n=2^(5-1)*5^(3-1)=400 Ответ: 400 и 2500 4.Найдите НОД чисел вида р^2-1, где р- простое число, большее 3, но меньшее 2011 Решение: р^2-1=(p-1)*(p+1), раз р-простое,то (р-1),(р+1)- четные. Значит одно из них делится на 4. Из трех последовательных чисел (р-1);р;(р+1) ровно одно делится на 3. А раз р-простое, большее 3, то это либо (р-1), либо (р+1). Значит (р-1),(р+1) делится на ( 2*2*2*3)=24. Ответ: 24.

3. Последовательности

Занумерованный ряд чисел a1, a2, a3, …, an - называется числовой последовательностью.

Существует три основных способа задания последовательности.

1. Аналитический. Последовательность задается формулой n-го члена; например, формулой аn = n * 7 задается последовательность а1, а2, …, аn, у которой а1 = 7; а2 = 14 и тд.

Примеры числовых последовательностей:

2, 4, 6, 8, 10, … , 2n, … ;

1, 4, 9, 16, 25, … , n² , … ;

1, 1/2, 1/3, 1/4, 1/5, … , 1/n , …

2. Рекуррентный. Любой член последовательности выражается через предшествующие члены. При данном способе задания последовательности обязательно указывается первый член последовательности и формула, которая позволяет вычислить любой член последовательности по известным предыдущим членам.

3. Словесный. Это задание последовательности описанием.

Арифметическая прогрессия.

Последовательность, у которой задан первый член a1, а каждый следующий равен предыдущему, сложенному с одним и тем же числом d, называется арифметической прогрессией:

a_n+1 = a_n + d, где d - разность прогрессии.

- Если d 0, то прогрессия является возрастающей. Если d

- Арифметическая прогрессия считается конечной, если рассматриваются только ее первые несколько членов.

Формулы арифметической прогрессии:

a_n = a₁ + d(n - 1) - формула n-го члена арифметической прогрессии;

2a_n = a_n-1 + a_n+1 - характеристическое свойство арифметической прогрессии для трех последовательных чисел;

a_n = a_k + d(n - k) - формула нахождения n-го члена арифметической прогрессии через k -ый член прогрессии;

a_n + a_m = a_k + a_l, - характеристическое свойство арифметической прогрессии для четырех произвольных чисел, если n + m = k + l.

Сумма n членов арифметической прогрессии:

Sn=1/2 (a₁+a_n)n

Sn=1/2 (2a₁+d(n−1))n

Геометрическая прогрессия.

Последовательность (bn), у которой задан первый член b₁ǂ0, а каждый следующий равен предыдущему, умноженному на одно и то же число qǂ0 , называется геометрической прогрессией:

b_n+1=b_nq , где q - знаменатель прогрессии

- Если |q| 1, то прогрессия называется возрастающей. Если |q|

- Геометрическая прогрессия считается конечной, если рассматриваются только ее первые несколько членов.

Формулы геометрической прогрессии

b_n=b_{1 *} qⁿ⁻¹ - формула n-го члена геометрической прогрессии.

b_n=b_{k *} q^n−k - формула n-го члена геометрической прогрессии через k-й член прогрессии.

b²_n=b_{n−1 *} b_n+1 - характеристическое свойство геометрической прогрессии для трех последовательных чисел.

b_{n *} b_m=b_{k *} b_l - характеристическое свойство геометрической прогрессии для четырех чисел, если n + m = k + l

Формулы суммы первых n членов геометрической прогрессии

S_n=b₁(qⁿ−1)/q-1

Решение задач:

4. Решение уравнений в целых числах.

Неопределенные уравнения – уравнения, содержащие более одного неизвестного. Под одним решением неопределенного уравнения понимается совокупность значений неизвестных, которая обращает данное уравнение в верное равенство.

Для решения в целых числах уравнения вида ах + by = c, где а, b, c – целые числа, отличные от нуля, приведем ряд теоретических положений, которые позволят установить правило решения. Эти положения основаны также на уже известных фактах теории делимости.

Теорема 1. Если НОД(а, b) = d, то существуют такие целые числа х и у, что имеет место равенство ах + bу = d. (Это равенство называется линейной комбинацией или линейным представлением наибольшего общего делителя двух чисел через сами эти числа.)

Доказательство теоремы основано на использовании равенства алгоритма Евклида для нахождения наибольшего общего делителя двух чисел (наибольший общий делитель выражается через неполные частные и остатки, начиная с последнего равенства в алгоритме Евклида).

Пример.

Найти линейное представление наибольшего общего делителя чисел 1232 и 1672.

Решение.

1. Составим равенства алгоритма Евклида:

1672 = 1232 ∙1 + 440,

1232 = 440 ∙ 2 + 352,

440 = 352 ∙ 1 + 88,

352 = 88 ∙ 4, т.е. (1672,352) = 88.

2) Выразим 88 последовательно через неполные частные и остатки, используя полученные выше равенства, начиная с конца:

88 = 440 - 352∙1 = (1672 - 1232) - (1232 - 1672∙2 + 1232∙2) = 1672∙3 - 1232∙4, т.е. 88 = 1672∙3 + 1232∙(-4).

Теорема 2. Если уравнение ах + bу = 1, если НОД(а, b) = 1, достаточно представить число 1 в виде линейной комбинации чисел а и b.

Справедливость этой теоремы следует из теоремы 1. Таким образом, чтобы найти одно целое решение уравнения ах + bу = 1, если НОД (а, в) = 1, достаточно представить число 1 в виде линейной комбинации чисел а и в.

Пример.

Найти целое решение уравнения 15х + 37у = 1.

Решение.

1. 37 = 15 ∙ 2 + 7,

15 = 7 ∙ 2 + 1.

2. 1 = 15 - 7∙2 = 15 - (37 - 15∙2) ∙2 = 15∙5 + 37∙(-2),

т.е. х= 5, у= -2 - решение данного уравнения.

Теорема 3. Если в уравнении ах + bу = с НОД(а, b) = d1 и с не делится на d, то уравнение целых решений не имеет.

Для доказательства теоремы достаточно предположить противное.

Пример.

Найти целое решение уравнения 16х - 34у = 7.

Решение.

(16,34)=2; 7 не делится на 2, уравнение целых решений не имеет

Теорема 4. Если в уравнении ах + bу = с НОД(а, b) = d1 и сd, то оно равносильно уравнению ах + bу = с, в котором НОД(а, b) = 1.

При доказательстве теоремы следует показать, что произвольное целое решение первого уравнения является также решением второго уравнения и обратно.

Теорема 5. Если в уравнении ах + bу = с НОД(а, b) = 1, то все целые решения этого уравнения заключены в формулах:

х = хс + bt, у = yc-at, где х, y - целое решение уравнения ах + bу = 1,

t – любое целое число.

При доказательстве теоремы следует показать, во-первых, что приведенные формулы действительно дают решения данного уравнения и, во-вторых, что произвольное целое решение этого уравнения заключено в приведенных формулах.

Приведенные теоремы позволяют установить следующее правило решения в целых числах уравнения ах+ bу = с НОД(а, b) = 1:

1. Находится целое решение уравнения ах + bу = 1 путем представления 1 как линейной комбинации чисел а и b (существуют и другие способы отыскания целых решений этого уравнения, например при использовании цепных дробей);

2. Составляется общая формула целых решений данного уравнения х = хс + bt, у = yc - at, где х, y - целое решение уравнения ах + bу = 1, t – любое целое число.

Придавая t определенные целые значения, можно получить частные решения данного уравнения: наименьшие по абсолютной величине, наименьшие положительные (если можно) и т.д.

Пример.

Найти целые решения уравнения 407х - 2816у = 33.

Решение.

1. Упрощаем данное уравнение, приводя его к виду 37х - 256у = 3.

2.Решаем уравнение 37х - 256у = 1.

256 = 37∙ 6 + 34,

37 = 34 ∙1 + 3,

34 = 3 ∙11 + 1.

1 = 34 - 3∙11 = 256 - 37∙6 - 11 (37 – 256 + 37∙6) = 256∙12 - 37∙83 =

= 37∙(-83) - 256∙(-12),

т.е. х= -83, y= -12.

3. Общий вид всех целых решений данного уравнения:

х = -83∙3 - 256t = -249 - 256t,

у = -12∙3 - 37 t = -36 - 37 t.

Положив t = -1, получим х= 7, у= 1 и общие формулы решений примут вид: х = 7 - 256t, у = 1-37t.

Метод полного перебора всех возможных значений переменных,

входящих в уравнение.

Найти множество всех пар натуральных чисел, которые являются решениями уравнения 49х + 51у = 602.

Решение:

Выразим из уравнения переменную х через у х =, так как х и у – натуральные числа, то х = 602 - 51у ≥ 49, 51у≤553, 1≤у≤10.

Полный перебор вариантов показывает, что натуральными решениями уравнения являются х=5, у=7.

Ответ: (5;7).

Решение уравнений методом разложения на множители.

Диофант наряду с линейными уравнениями рассматривал квадратные и кубические неопределенные уравнения. Решение их, как правило, сложно.

Рассмотрим такой случай, когда в уравнениях можно применить формулу разности квадратов или другой способ разложения на множители.

Решить уравнение в целых числах: х² + 23 = у²

Решение:

Перепишем уравнение в виде: у² - х² = 23, (у - х)(у + х) = 23

Так как х и у – целые числа и 23 – простое число, то возможны случаи:

Решая полученные системы, находим:

Выражение одной переменной через другую и выделение целой части дроби.

Решить уравнение в целых числах: х² + ху – у – 2 = 0.

Решение:

Выразим из данного уравнения у через х:

у(х - 1) =2 - х²,

у = = – = – = – += -(х + 1) + , (х1)

Так как х, у – целые числа, то дробь должна быть целым числом.

Это возможно, если х – 1 =

1) 2)

Ответ: (0;-2);(2;-2).

Ответ: (-11;12);(11;12);(11;-12);(-11;-12).

Методы, основанные на выделении полного квадрата.

Найдите все целочисленные решения уравнения: х² - 6ху + 13у² = 29.

Решение:

Преобразуем левую часть уравнения, выделив полные квадраты,

х² - 6ху + 13у² = (х² - 6ху + 9у²) + 4у² = (х - 3у)² + (2у)² = 29, значит (2у)² 29.

Получаем, что у может быть равен 0; .

1. у = 0, (х - 0)² = 29. Не имеет решений в целых числах.

2. у = -1, (х + 3)² + 4 = 29, (х + 3)² = 25, х + 3 = 5 или х + 3 = -5

х=2 х=-8

3. у = 1, (х - 3)² +4 =29,

(х - 3)² =25, х – 3 = 5 или х – 3 = -5

х = 8 х = -2

4. у = -2, (х + 6)² + 16 = 29, (х + 6)² = 13. Нет решений в целых числах.

5. у=2, (х-6)²+16=29, (х-6)²=13. Нет решений в целых числах.

Ответ: (2;-1); (-8;-1); (8;1); (-2;1).

Решение уравнений с двумя переменными как квадратных

относительно одной из переменных.

Решить уравнение в целых числах: 5х²+5у²+8ху+2у-2х+2=0.

Решение:

Рассмотрим уравнение как квадратное относительно х:

5х² + (8у - 2)х + 5у² + 2у + 2 = 0

D = (8у - 2)² - 4·5(5у² + 2у + 2) = 64у² - 32у + 4 = -100у² - 40у – 40 = = -36(у² + 2у + 1) = -36(у + 1)²

Для того, чтобы уравнение имело решения, необходимо, чтобы D = 0.

-36(у + 1)² = 0. Это возможно при у = -1, тогда х = 1.

Ответ: (1;-1).