Решение задач в целых числах

Московский государственный технический университет имени Н.Э. Баумана








                РЕШЕНИЕ ЗАДАЧ В ЦЕЛЫХ ЧИСЛАХ





Рекомендовано Научно-методическим советом МГТУ им. Н.Э. Баумана в качестве учебного пособия













Москва Издательство МГТУ им. Н.Э. Баумана 2013

УДК 511(075.8)
ББК 22.131
     Р47


Авторы: Н.И. Латанова, А.П. Власова, Н.В. Евсеева, М.Е. Старостина

Рецензенты: И.В. Блудова, З.Н. Русакова



          Решение задач в целых числах : учеб. пособие / Н.И. Ла-Р47 танова и др. — М. : Изд-во МГТУ им. Н.Э. Баумана, 2013. — 53, [3] с.
           ISBN 978-5-7038-3652-1
           Рассмотрены задачи на делимость чисел, четность, а также задачи, связанные с использованием метода математической индукции. Приведены задачи для самостоятельного решения с ответами.
           Для учащихся старших классов средней школы, абитуриентов вузов.



УДК 511(075.8)
ББК 22.131
















ISBN 978-5-7038-3652-1

© МГТУ им. Н.Э. Баумана, 2013

ПРЕДИСЛОВИЕ

    Учебное пособие посвящено задачам повышенной сложности, требующим нестандартных методов решения, связанных с элементами теории чисел.
    Задачи, содержащие элементы теории чисел, являются неотъемлемой частью Единого государственного экзамена (ЕГЭ) и олимпиад по математике. Однако учебных пособий, в которых изложение теории чисел сопровождается разбором конкурсных задач и задач ЕГЭ, явно недостаточно.
    Авторы учебного пособия ставят своей целью ознакомить школьников с различными методами решения на первый взгляд трудных задач, проиллюстрировать широкие возможности использования хорошо усвоенных в младших классах школьных знаний, полученных при изучении натуральной и целочисленной арифметики.
    В настоящем пособии рассмотрены задачи на делимость чисел, четность, а также задачи, связанные с записью числа и различным представлением чисел с использованием метода математической индукции. Разобрано большое количество примеров, конкурсных задач, приведены задачи для самостоятельного решения с ответами и указаниями.
    Учебное пособие адресовано учащимся старших классов средней школы, абитуриентам вузов, слушателям подготовительных курсов и преподавателям математики. Оно может быть использовано учащимися для подготовки к ЕГЭ и к олимпиадам по математике.
    Авторы надеются, что внимательно изучивший это учебное пособие старшеклассник без труда решит подобные задачи.
    Желаем успеха!

Глава 1. ПРОСТЫЕ ЧИСЛА

    Натуральное число, большее единицы, называется простым, если оно делится только на единицу и на само себя и других натуральных делителей не имеет. Натуральные числа, большие единицы и не являющиеся простыми, называются составными.
    Запишем ряд простых чисел: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31... Простых чисел бесконечно много. Отметим, что число 2 — единственное четное простое число, все остальные простые числа нечетные.
    Основная теорема арифметики. Каждое составное число разлагается в произведение нескольких простых чисел, необязательно различных, причем такое разложение единственно с точностью до порядка сомножителей:
                     ⁿ = рГ¹ Р 2 ² ••• p*s, где s — количество простых сомножителей.
    Следствие 1.1. Если произведение двух целых чисел делится на простое число p, то хотя бы одно из этих чисел делится на число p. В частности, если число a² делится на число b², то число а делится на число b. Действительно, все простые множители входят с четными показателями в канонические разложения чисел а² и b². Поэтому если а² - kb², то все простые множители входят в каноническое разложение числа k также с четными показателями, и, значит, число k является точным квадратом. Из равенства а² - n²b² следует, что а — nb, т. е. число а делится на число b.
    Следствие 1.2. Если число n g N делится на натуральные числа b и c и числа b и с взаимно простые, то число n делится на произведение bc.
    Следствие 1.3. Число а g N делится на число b g N тогда и только тогда, когда все простые множители, входящие в разложение числа b, входят и в разложение числа а, причем с показателем степени не меньшим, чем в разложении числа b.


4

    Для того чтобы вычислить количество натуральных делителей числа n е N, используют формулу

    т(п) = (ttj +1) (а₂ + 1)-(а, +1).        (1.1)

    Рассмотрим число n, которое раскладывается в произведение простых множителей (n - pj*¹ pа), и определим, сколько у него делителей. Для удобства запишем все делители в двумерную табл. 1.1.
Таблица 1.1

а2_---'' 0     1       2       K|  
/«1                                
   0     1    p 2      2       ао  
                      p 2     p 2  
   1     p1 p1 p 2  p1 p 2     а,  
                             p1 p 2
                                   
  а 2    а   а1 а?   а1 а9   ал а.2
         Г! p1' p 2 p1' p 2  Ж p 2 

Из табл. 1.1 ясно, что количество делителей числа п равно т( n) - (а1 + 1)(а₂ +1).

    Если n — pf¹ pа² ■ • ■ pSas, то табл. 1.1 из двумерной становится S-мерной и количество делителей будет равно т(n) -⁻(а1 + 1)(а2 + 1)---(а s + 1).
    В табл. 1.1 каждая строка и каждый столбец являются геометрической прогрессией со знаменателем pₛ, поэтому после преобразований сумма делителей числа п


    п⁽ n⁾⁻


  а +1       аг+1

    А¹ -¹ pₛs -¹ ---------- ---------        A ⁻¹       pₛ ⁻¹


(1.2)

    Для того чтобы найти показатель простого числа р в каноническом разложении числа n!, можно использовать формулу Лежандра


n
p

n

n

+

а -

+ ...,

p³

(1.3)


где знаком «[ ]» обозначена целая часть числа.


5

    Пример 1.1. Пусть n = pa, где p — простое число, a g N. Вычислить c( n) — сумму делителей числа п.
    Запишем все делители числа п в табл. 1.2, из которой следует, что c( n) — сумма членов геометрической прогрессии со знаменателем p. Тогда с помощью формулы суммы геометрической прогрессии получим

   a      -I          
   p \ p - 1          
cl n) =--------.      
    v 7 p -1          
     Таблица 1.2      
 a   0  1   2     a  
P a  1  P  P2    P a 

    Перейдем к рассмотрению задач на простые числа.
    Пример 1.2. Найти наименьшее натуральное решение следующих уравнений:

    т( x ) = 6; т( x ) = 10; т( x ) = pq,

где q > p; q, p — простые числа.
    Напомним, что символом т(х) обозначается количество делителей числа х.
    Если т(x) - 6, то число х представим в виде

a a     a,
x = pi1 p 2 — pₛs .
При этом

    т(x) = (a1 + 1)(a₂ +1) — (as +1) = 2 ■ 3.

Отсюда a1 = 1, a₂ = 2. Поэтому x = 2 ■ 3² = 18 или x = 2² ■ 3 = 12.
    Следовательно, наименьшим натуральным решением будет 12.
    Если т(x) = 10, то число х представим в виде

a.1 «2  О.
x = p11 p 2 — pₛs .


6