Лекция 4: Теория чисел

Вид материала

Содержание

Основное свойство
Основное свойство
Алгоритм Евклида.
Арифметика остатков и определение сравнения.

Подобный материал:

Лекция 4: Теория чисел.

Простые и составные числа. Основная теорема арифметики:

Из школьной программы нашим читателям, безусловно, должны быть известны следующие факты:
- натуральное число называется простым, если оно делится только на самого себя и на 1;
- натуральное число называется составным, если оно имеет делитель, отличный от самого себя и 1;
- 1 не считается ни простым, ни составным числом (это связано с тем, что 1 является так называемым обратимым элементом множества целых чисел, т.е. любое число можно поделить на 1, а простые числа этим свойством не обладают);
- любое натуральное число, отличное от 1, можно разложить в произведение простых сомножителей, причем единственным образом (с точностью до перестановки сомножителей) - этот факт называется основной теоремой арифметики.

Вместе с этими фактами следует помнить и следующие:
- составные числа имеют в своем разложении на простые множители хотя бы 2 (не обязательно разных!) множителя, простые - ровно 1 множитель, единица - 0 множителей (!);
- для любого простого числа (p) и любого натурального числа (n) существует целая неотрицательная степень вхождения p в разложение n, и она определена однозначно; если в разложении n нет множителя p, то степень равна 0, если есть - степень вхождения равна количеству простых множителей, равных p, в разложении n (здесь и далее мы повсеместно будем обозначать эту степень вхождения через v_p(n), как принято в высшей алгебре; более того, это сделано специально, чтобы читатели хорошо овладели удобным и кратким языком этих обозначений);
- 2 натуральных числа a и b равны тогда и только тогда, когда v_p(a)=v_p(b) для любого простого p (по-русски: "два числа равны тогда и только тогда, когда степени вождения в них всех простых множителей одинаковы");
- если натуральное число n=a*b, то для любого простого p: v_p(n)=v_p(a)+v_p(b) (по-русски: "степень вхождения любого простого множителя в число n равна сумме его степеней вхождения в a и b"); это следует из того, что разложение произведения чисел на простые множители есть объединение их разложений;
- число n делится на число d если и только если любой простой множитель входит в n в не меньшей степени, чем в d, т.е. v_p(n)>=v_p(d) для любого простого p; иначе, если для какого-то множителя p это неверно, то при делении образуется дробь с неуничтожаемым множителем p в знаменателе;
- последнее условие достаточно проверять, разумеется, только для простых множителей входящих в разложение d; для невходящих будет v_p(d)=0, что в любом случае не больше v_p(n);
- при этом, если n делится на d, и частное мы обозначим за q, то v_p(q)=v_p(n)-v_p(d) для любого простого p (по-русски: "степень вхождения любого простого множителя в число q равна разности его степеней вхождения в n и d"); это следует из равенства n=d*q и предыдущих пунктов;
- да, чуть не забыл: для любого простого p, v_p(1)=0 (по-русски: "степень вхождения любого простого множителя в единицу равна нулю").

(!) Буква p (а также буква q) в этой лекции будет специально зарезервирована для обозначения только простых чисел. Поэтому слова "для всех p", "для любого q" и т.п. следует понимать как "для всех простых p", "для любого простого q".

Примеры:
Типичные простые числа: 2, 3, 5, 7, 11, 13, 17, 19, 101, 239... (во многих учебниках и справочниках есть полная таблица простых чисел от 1 до 1000; а всего простых чисел бесконечно много).
Типичные составные числа: 4, 6, 8, 10, 12... (делятся на 2), 9, 15, 21, 27... (делятся на 3), 25, 35, 55, 65... (делятся на 5). Нетипичные: 111=37*3, 1001=7*11*13, 10001=73*137... (составных чисел тоже бесконечно много, хотя бы потому, что четных - бесконечно много).
А простого способа определить по виду числа его простоту (если для него не выполняется ни один из признаков делимости на маленькие числа) не существует(!).
Разложение на простые множители - это что-то типа: 72=2*2*2*3*3=2³*3²; здесь мы имеем v₂(72)=3, v₃(72)=2 и v_p(72)=0 для простого p, отличного от 2 и 3.
Если написать, например, 72=6*12, то для этих чисел будут разложения: 6=2*3, 12=2*2*3==2²*3. Тогда получаем: v₂(6)=1, v₂(12)=2, v₃(6)=1, v₃(12)=1, v_p(6)=v_p(12)=0, при p, не равном 2 и 3.
Заметим, что 1+2=3, 1+1=2 и 0+0=0, в соответствии с формулой v_p(n)=v_p(a)+v_p(b) для n=a*b.
Рассмотрим, например, число 18=2*3*3=2*3² - у него будет здесь мы имеем v₂(18)=1, v₃(18)=2 и v_p(18)=0 для всех прочих множителей. 3>=1, 2>=2, 0>=0, поэтому v_p(72)>=v_p(18) для любого p. И при этом, действительно, 72 делится на 18.
Частное от деления 72 на 18 равно 4=2*2=2², и у него v₂(4)=2, v₃(4)=0, v_p(4)=0 для p, не равного 2 и 3. Как ни странно, 2=3-1, 0=2-2, 0=0-0, т.е. все согласуется с формулой v_p(q)=v_p(n)-v_p(d) для q=n/d.
Если рассмотреть число, на которое 72 вообще не делится, например 48, то оно равно 2*2*2*2*3=2⁴*3. Тогда v₂(48)=4>3=v₂(72). Именно из-за этого оно и не делится (72/48=3/2 - как раз остается 2 в знаменателе).

Разложение на простые множители и вопросы делимости:
Свойства делимости числа полностью определяются его разложением на простые множители. Более того, как показывает ряд следующим примеров, это свойства удобнее проверять именно через разложение.

(!) Утверждение "a делится на b" или "b делит a" мы будем записывать общепринятым обозначением b|a. Другое общепринятое обозначение - вертикальное троеточие - мы по техническим причинам использовать не будем.

1. Делится ли 2⁹*3 на 8? А делится ли оно на 9? А на 6?
На 8 это число делится, т.к. 2 входит в его разложение на множители в степени 9, а 8=2³.
На 9 это число не делится, так как 3 входит в его разложение на множители только в степени 1, а 9=3².
На 6 оно делится, потому что 6=2*3, а в разложение данного числа на множители входят 2 и 3, каждое в степени не меньше 1.

2. Верно ли, что если натуральное число делится на 3 и на 4, то оно делится на 12? А верно ли, что если число делится на 4 и на 6, то оно делится на 24?
Первое утверждение верно: если 4|n, то v₂(n)>=2. Кроме того, 3|n, и поэтому v₃(n)>=1. Тогда ясно, что n делится на 2²*3=12 ч.т.д.
Второе утверждение неверно: Если 4|n, то v₂(n)>=2. Если 6|n, то v₂(n)>=1 и v₃(n)>=1. В общей сложности получается, что v₃(n)>=1, а v₂(n)>=max(1,2)=2 (важно, что тут максимум, а не сумма!). Тогда n делится на 2²*3=12, но не обязательно на 24. Действительно, числа 12, 36, 60, 84... делятся на 4 и на 6, делятся, как и было доказано, на 12, но они не делятся на 24.

3. Число 5А делится на 3. Верно ли, что А делится на 3? А верно ли, что если 15А делится на 6, то А делится на 6?
Первое утверждение верно: если 3|5А, то v₃(5A)>=1. v₃(5)=0 (5 на 3 не делится), откуда v₃(A)=v₃(5A)-v₃(5)>=1, т.е. 3|A, ч.т.д.
Второе утверждение неверно: 6=2*3, откуда v₂(15A)>=1, v₃(15A)>=1. Но 3 входит и в разложение числа 15, поэтому v₃(A)=v₃(15A)-v₃(15)=v₃(15A)-1>=0, т.е. может быть и нулем - тогда неверно 6|A. Например, так будет при А=2: 15А=30, 6|30 (а 2|A, т.к. 15 на 2 не делится).

Взаимная простота. НОК и НОД. 2 целых числа называются взаимно простыми, если у них нет общих делителей, кроме 1 (и -1). Это кратко записывается как (m,n)=1.

1. 2 числа взаимно просты тогда и только тогда, когда в их разложении нет общих простых множителей (наборы простых множителей не пересекаются). Это очевидно, поскольку любой общий простой множитель будет общим делителем, отличным от 1 и -1, а любой общим делитель, отличный от 1 и -1, делится на какой-то простой множитель, который и будет общим.

(!) Любые 2 различных простых числа взаимно просты.

2. Если m|A, n|A и (m,n)=1, то mn|A. Действительно, делимость A на m и n означает v_p(A)>=v_p(m) и v_p(A)>=v_p(n), то есть v_p(A)>=max(v_p(m),v_p(n)). По п.1 все простые множители m и n различны. Поэтому, если какое-то p входит, например, в разложение m (v_p(m)>0), то в разложение n оно не входит (v_p(n)=0). Отсюда нетрудно заметить, что max(v_p(m),v_p(n))=v_p(m)+v_p(n)=v_p(mn) для всех p, входящих в разложение m или n, т.е. входящих в разложение mn. Тогда для таких p v_p(A)>=v_p(mn), откуда mn|А, ч.т.д.

2'. Вообще говоря, (m,n)=1 равносильно max(v_p(m),v_p(n))=v_p(m)+v_p(n) для всех p (то есть, так записывается взаимная простота в терминах степеней вхождения). То, что это равенство имеет место для взаимно простых m и n, мы уже проверяли (и для множителей, не входящих в разложение m или n, это тоже верно: max(v_p(m),v_p(n))=max(0,0)=0=0+0=v_p(m)+v_p(n)). Теперь пусть это равенство верно: из двух чисел v_p(m), v_p(n) большее всегда равно их сумме. Тогда, конечно, меньшее равно нулю. При таком условии быть одновременно ненулевыми эти числа не могут. Значит, нет такого p, которое одновременно входит в разложение m и n. А это, по п.1, и означает взаимную простоту.

3. Если A|mn и (A,m)=1, то А|n. Действительно, т.к. A|mn, то v_p(mn)>=v_p(A) для всех p. (m,A)=1, поэтому для всех p, входящих в разложение A, v_p(m)=0 (такое рассуждение здесь уже было). Значит, v_p(n)=v_p(mn)>=v_p(A) для всех таких p, откуда А|n, ч.т.д.

Наибольшим общим делителем (НОД) двух чисел называется наибольшее натуральное число, на которое делятся они оба. Например, НОД(2,3)=1, НОД(12,18)=6, НОД(1,n)=1, НОД(n,n)=n, НОД(0,n)=n (для любого натурального n). НОД(0,0) не определен. Для краткости часто вместо НОД(a,b) пишется просто (a,b).
(!) Если a и b взаимно просты, то НОД(a,b)=1, что и поясняет смысл обозначения (a,b)=1.
Основное свойство: НОД 2-х чисел - это произведение всех простых множителей этих чисел, каждый из которых взят в минимальной из степеней вхождения в эти числа (т.е. v_p((a,b))=min(v_p(a),v_p(b)) для любого простого p). Действительно, пусть d - любой общий делитель. Т.к. d|a, то v_p(d)<=v_p(a), т.к. d|b, то v_p(d)<=v_p(b). Отсюда v_p(d)<=min(v_p(a),v_p(b)). Понятно, что общий делитель будет наибольшим, если эти неравенства превратятся в равенства (и тогда он еще остается делителем). Значит, НОД 2-х чисел - это именно то, что утверждалось в формулировке свойства ч.т.д.
Следствие: НОД 2-х чисел делится на любой общий делитель этих чисел. Действительно, для любого общего делителя d чисел a и b верно неравенство v_p(d)<=min(v_p(a),v_p(b))=v_p((a,b)) при всех p. Значит, этот делитель явлется делителем НОД, ч.т.д.

Наименьшим общим кратным (НОК) двух чисел называется наименьшее натуральное число, которое делятся на их оба. Например, НОК(2,3)=6, НОД(12,18)=36, НОК(1,n)=n, НОК(n,n)=n, НОК(0,n) не определен (для любого натурального n). Для краткости часто вместо НОК(a,b) пишется просто [a,b].
(!) Если a и b взаимно просты, то НОК(a,b)=ab. Это можно понять многими способами. Например, согласно св-ву 2 взаимной простоты, любое общее кратное a и b будет делиться на ab, поэтому никакое число, меньшее ab, общим кратным не будет, а само ab - конечно, будет.
Основное свойство: НОК 2-х чисел - это произведение всех простых множителей этих чисел, каждый из которых взят в максимальной из степеней вхождения в эти числа (т.е., v_p([a,b])=min(v_p(a),v_p(b)). Действительно, пусть k - любое общее кратное. Т.к. a|k, то v_p(a)<=v_p(k), т.к. b|k, то v_p(b)<=v_p(k). Отсюда v_p(k)>=max(v_p(a),v_p(b)). Понятно, что общее кратное будет наибольшим, если эти неравенства превратятся в равенства (и тогда оно еще остается кратным). Значит, НОК 2-х чисел - это именно то, что утверждалось в формулировке свойства ч.т.д.
Следствие: любое общее кратное 2-х чисел делится на НОК этих чисел. Действительно, для любого общего кратного k чисел a и b верно неравенство v_p(k)>=max(v_p(a),v_p(b))=v_p([a,b]) при всех p. Значит, это кратное делится на НОК, ч.т.д.

Примеры:

Задача 1. 8a=13b. Докажите, что a+b-составное число (a и b - натуральные).
Решение: Заметим, что числа 8 и 13 взаимно просты. Тогда, поскольку 13|8a, то 13|a (свойство 3 взаимно простых чисел). Аналогично, поскольку 8|13b, то 8|b. Тогда существуют k и l - частные от этих делений такие, что a=13k, b=8l. Перепишем равенство в виде 8*13k=13*8l, т.е. 104k=104l. Отсюда k=l и b=8k. А тогда a+b=13k+8k=21k. Поскольку 21 - составное число, то 21k составное при любом натуральном k ч.т.д.

(!) Очень ценное соображение: всегда, если xa=yb и x и y взаимно просты, то y|a и x|b.

Задача 2. Докажите, что НОК(a,b)*НОД(a,b)=ab для любых натуральных a и b.
Решение: Докажем это равенство стандартным для задач по теории чисел путем: проверим равенство v_p((a,b)*[a,b])=v_p(ab) при любом p. Мы уже знаем, что v_p(ab)=v_p(a)+v_p(b), а v_p((a,b)*[a,b])=v_p((a,b))+v_p([a,b])=min(v_p(a),v_p(b))+max(v_p(a),v_p(b)). Осталось заметить, что сумма минимума и максимума из двух чисел всегда равна сумме этих чисел... и доказательство готово.

Для тех, кто так и не понял последнего перехода: пусть k и l - два числа (даже не обязательно целых). Пусть, например, k - большее из них (k>=l). Тогда max(k,l)=k, min(k,l)=l и min(k,l)+max(k,l)=l+k=k+l.

Задача 3. Докажите, что произведение любых трех последовательных натуральных чисел делится на 6.
Решение: Среди трех последовательных чисел есть хотя бы одно четное (если наименьшее - нечетное, то четным обязательно будет среднее), поэтому их произведение делится на 2. Кроме того, среди этих чисел обязательно есть хотя бы одно, делящееся на 3 (обозначим наименьшее число за n; если n на 3 не делится, то оно либо дает при делении на 3 остаток 1, и n+2 - наибольшее число - делится на 3, либо остаток 2, и n+1 - среднее число - делится на 3), поэтому их произведение делится на 3. Поскольку 2 и 3 взаимно просты, то произведение 3-х последовательных чисел делится на 2*3=6.

Алгоритм Евклида. Еще древнегреческий математик Евклид изобрел способ нахождения НОД больших чисел, не зная их разложения на простые множители. Его основная идея: если r - остаток отделения a на b, то НОД(a,b)=НОД(b,r). Действительно, a=bq+r, откуда НОД(a,b)|r. Понятно, что НОД(a,b)|b, и поэтому НОД(a,b)|НОД(b,r). Аналогично и НОД(b,r)|НОД(a,b). Значит, НОД(a,b)=НОД(b,r), ч.т.д. Гениальная идея Евклида состоит в том, что можно делить так много раз подряд: каждый раз делитель от предыдущего деления будем делить с остатком на остаток от предыдущего деления. Поскольку числа все время уменьшаются, то за конечное число шагов (не больше величины исходных чисел) мы получим нулевой остаток. Тогда предыдущий остаток d перед ним и будет равен НОД. Действительно, НОД(a,b)=НОД(b,r)=...=НОД(d,0)=d ч.т.д.

Примеры:

Задача 1. Найти НОД(1381955,690713).
Решение: Будем делить с остатком по алгоритму Евклида. 1381955=2*690713+529, откуда НОД(1381955,690713)=НОД(690713,529). Теперь 690713=1305*529+368, откуда НОД(690713,529)=НОД(529,368). Далее, 529=368+161, откуда НОД(529,368)=НОД(368,161). Делим еще раз: 368=2*161+46, откуда НОД(368,161)=НОД(161,46). И еще раз: 161=3*46+23, откуда НОД(161,46)=НОД(46,23). Наконец, 46=2*23 - остаток 0, значит НОД был равен предыдущему остатку, т.е. 23. Для сравнения: разложение на простые даст нам 1381955=5*23*61*197, 690713=23*59*509 - и его нахождение представляет собой долгое упражнение с калькулятором!

Задача 2. Доказать, что дробь (2n+13)/(n+7) несократима.
Решение: Будем находить НОД числителя и знаменателя по алгоритму Евклида. Как ни странно, это помогает и для выражений, содержащих неизвестные. 2n+13=(n+7)+(n+6), откуда НОД(2n+13,n+7)=НОД(n+7,n+6). Теперь n+7=(n+6)+1, откуда НОД(n+7,n+6)=НОД(n+6,1)=1. Ответ будет 1, вне зависимости от значения n. Таким образом, числитель и знаменатель всегда взаимно просты, что и означает несократимость дроби.

Арифметика остатков и определение сравнения. Также одна из самых распространенных идей в олимпиадной теории чисел - это то, что называется "вычисления в кольце вычетов". Проще говоря, вместо того, чтобы складывать, вычитать и умножать числа, можно проводить те же операции с остатками от их деления на какое-либо число - и результат будет давать тот же остаток от деления на это число, что и результат исходных вычислений. Более того, все промежуточные результаты, если они становятся большими, можно заменять на их остатки от деления. Наконец, мы не обязаны заменять именно на остатки - можно брать любые числа, которые дают те же остатки. Главное при этом:
- не применять это к операции деления (а если совсем необходимо, то искать частное по определению: это такое число, которое, будучи умноженным - по модулю - на делитель, дает делимое);
- не менять модуль, по которому производится вычисление, т. е. на разных этапах одного и того же вычисления брать остатки от деления на одно и то же число.

Определение: Назовем 2 целых числа a и b сравнимыми по модулю n, если их разность делится на n, или, что то же самое, остатки от деления этих чисел на n одинаковы. (Мы будем записывать это как a=b (mod n), хотя чаще ставится знак тождественного равенства).

(!) Утверждение "n дает остаток r от деления на d" кратко записывается как n=r (mod d).

1. Сумма двух любых целых чисел и сумма чисел, сравнимых с ними по модулю n, сравнимы по модулю n.
Действительно, пусть a=b (mod n), c=d (mod n) - такие же обозначения будут и в следующих пунктах. Тогда, по определению сравнимости, n|a-b и n|c-d. Легко заметить, что сумма двух чисел, делящихся на n, делится на n, то есть n|(a-b)+(c-d)=(a+c)-(b+d). Но это ровно и означает, что a+c=b+d (mod n) ч.т.д.

2. Разность двух любых целых чисел и разность чисел, сравнимых с ними по модулю n, сравнимы по модулю n.
Доказывается точно так же, как предыдущее: только не сумма, а разность двух чисел, делящихся на n, тоже делится на n, поэтому n|(a-b)-(c-d)=(a-c)-(b-d).

3. Произведение двух любых целых чисел и произведение чисел, сравнимых с ними по модулю n, сравнимы по модулю n.
Здесь несколько посложнее: из a=b (mod n) и c=d (mod n) т.е. n|a-b и n|c-d надо вывести ac=bd (mod n), т.е. n|ac-bd. Делаем такой трюк: ac-bd=ac-ad+ad-bd=a(c-d)+(a-b)d. Из n|a-b следует n|(a-b)d, а из n|c-d - n|a(c-d). И из этих двух уже получаем n|a(c-d)+(a-b)d ч.т.д.

Примеры:

Задача 1. Доказать, что n³+2n делится на 3 при любом натуральном n.
Решение: Переберем все возможные остатки n от деления на 3 (перебор всех остатков действительно является полным решением!). Если n=0 (mod 3), т.е. n делится на 3, то n³ и 2n делятся на 3, откуда n³+2n делится на 3. Если n=1 (mod 3), то n³+2n=1³+2*1=1+2=3=0 (mod 3), т.е. делится на 3. Если же n=2 (mod 3), то n³+2n=2³+2*2=8+4=12=0 (mod 3) - тоже делится на 3. Значит, при любом n (поскольку любое n дает от деления на 3 остаток 0, 1 или 2) n³+2n делится на 3 ч.т.д.

Задача 2. Решить в целых числах: X³-Y³=17.
Решение: Воспользуемся тождеством: X³-Y³=(X-Y)(X²+XY+Y²). Оба множителя в правой части - целые при целых X и Y, а их произведение равно 17, поэтому они будут делителями числа 17. Поскольку это число простое, то нам надо рассмотреть только 4 случая:
1.) X-Y=1, X²+XY+Y²=17. Подставим во второе уравнение Y+1 вместо X: (Y+1)²+(Y+1)Y+Y²=17, то есть 3Y²+3Y+1=17 или 3(Y²+Y)=16. Но 16 не делится на 3, откуда следует отсутствие целых решений в этом случае.
2.) X-Y=17, X²+XY+Y²=1. Подставим во второе уравнение Y+17 вместо X: (Y+17)²+(Y+17)Y+Y²=1, то есть 3Y²+3*17Y+289=1, или 3(Y²+17Y)+288=0. Сократив на 3, получим Y²+17Y+96=0 - квадратное уравнение с дискриминантом 17²-4*96=289-384<0. Решений у этого уравнения нет вообще, даже нецелых.
3.) X-Y=-1, X²+XY+Y²=-17.
4.) X-Y=-17, X²+XY+Y²=-1. Случаи отрицательных делителей тоже всегда надо рассматривать. В данном случае (даже в двух) нам просто повезло: выражение X²+XY+Y² вообще не может быть отрицательным, откуда следует отсутствие решений. Действительно, если XY>=0, то X²+XY+Y²>=X²+Y²>=0, а если XY<=0, то X²+XY+Y²>=X²+2XY+Y²=(X+Y)²>=0 ч.т.д.

(!) Мы получили, что уравнение не имеет целых решений. Здесь стоит обратить внимание не только на общую идею решения уравнений в целых числах разложением на множители, но и на доказательство важного тождества X²+XY+Y²>=0.

Упражнение. (Для любителей теории чисел.) Решить в целых числах уравнение X²-Y²=232. Положительных решений у него должно быть ровно два: (X=59,Y=57), (X=31,Y=27). А остальные получаются из них естественным для такого уравнения способом - сменой знаков у X и Y.

Задача 3. Доказать, что если P и P²+2 - простые числа, то P³+2 - тоже простое число.
Решение: Нетрудно убедиться, что P=2 не подходит (P²+2 не простое), а P=3 подходит (и условие, и то, что надо доказать). Более того, никаких других подходящих P в первой десятке нет. На самом деле (как обычно и бывает в олимпиадных задачах) подходящих P>3 нет вообще. Действительно, если P>3, то P не делится на 3. Тогда P=1 (mod 3) или P=2 (mod 3). В любом случае, P²=1 (mod 3) и P²+2=0 (mod 3), т.е. делится на 3. Но тогда оно не может быть простым, так как оно явно больше трех! Утверждение доказано.

(!) Вообще, если p и q - два простых числа и p|q, то p=q, и никак иначе.

(!) Обратите внимание: это было типичное "липовое" условие, Хотя она формулируется "доказать, что из А следует В", но на самом деле доказывать надо, что А верно лишь для небольшого конечного количества наборов чисел. Дальше уже не составляет проблемы проверить, что для каждого из них верно условие В.

Задача 4. A+B+C делится на 6. Доказать, что A³+B³+C³ делится на 6.
Решение №1: Рассмотрим, какие остатки могут давать точные кубы по модулю 6. Рассматривая всевозможные остатки, получаем, что каждое число сравнимо с собственным кубом по модулю 6 (легче проверить отдельно, что N сравнимо с N³ по модулю 2 и по модулю 3). Тогда сумма трех чисел сравнима по модулю 6 с суммой их кубов. Первая сумма делится на 6, тогда и вторая делится на 6, ч.т.д.
Решение №2: Воспользуемся тождеством: A³+B³+C³=(A+B+C)(A²+B²+C²-AB-AC-BC)+3ABC (как его вывести, это отдельный алгебраический вопрос). Отсюда сразу следует, что если A+B+C делится на 6, то A³+B³+C³ сравнимо по модулю 6 с 3ABC. Нам осталось доказать, что 3ABC делится на 6, а это равносильно тому, что ABC четно. А ABC действительно четно: в противним случае все три числа A, B и C были бы нечетными, и их сумма тоже была бы нечетной и не могла бы делиться на 6?! ч.т.д.

Задача 5. Найти наименьшее натуральное число, дающее остатки 1 при делении на 2, 2 при делении на 3... 5 при делении на 6.
Решение: Обзовем наше число буквой N. Заметим, что наше условие означает, что N+1 - наименьшее число, которое делится на 2, 3, 4, 5 и 6 одновременно. Такое число - это 60=НОК(2,3,4,5,6). (НОК нескольких чисел определяется так же, как и у двух: наименьшее, которое одновременно делится на них все). Значит, искомое N равно 59.

Теорема. Натуральное число является точным квадратом тогда и только тогда, когда у него нечетное число делителей.
Доказательство: Возьмем натуральное число N и попробуем разбить его делители на пары. Если d|N, то число (N/d) - тоже делитель N. Объединим их в пару, и поступим так со всеми делителями. Либо все делители разбились на пары, либо какой-то делитель оказался парой к самому себе. Последнее означает, что у N есть делитель d, такой, что d=N/d, т.е. N=d². Понятно, что если N - не точный квадрат, то такого быть не может, и у N - четное число делителей. А если N - точный квадрат, то такое обязательно будет, причем ровно одно, и у N - нечетное число делителей ч.т.д.

Blog

Лекция 4: Теория чисел

Содержание