WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

   Добро пожаловать!


Pages:     | 1 |   ...   | 2 | 3 || 5 | 6 |   ...   | 27 |

3.58. Докажите, что если (a, b) = 1, то (2a + b, a(a + b)) = 1.

3.59. Докажите, что если (a, b) = 1, то наибольший общий делитель чисел a + b и a2 + b2 равен 1 или 2.

3.60. Пусть a и b — натуральные числа. Докажите, что среди чисел a, 2a, 3a,..., ba ровно (a, b) чисел делится на b.

32 3. Алгоритм Евклида и основная теорема арифметики 3.61. Пусть (a, b) = 1 и (x0, y0) — некоторое целочисленное решение уравнения ax + by = 1. Докажите, что все решения этого уравнения в целых числах получаются по формулам x = x0 + kb, y = y0 - ka, где k — произвольное целое число.

3.62. Как описать все решения в целых числах уравнения ax+by = c при произвольных a, b, c 3.63. Решите в целых числах уравнения (укажите все решения):

а) 45x - 37y = 25; г) 109x + 89y = 1;

б) 19x + 95y = 1995; д) 43x + 13y = 21;

в) 10x + 2y + 18z = 7; е) 34x - 21y = 1.

3.64. Докажите, что число шагов в алгоритме Евклида может быть сколь угодно большим.

3.65. Существует ли в сутках момент, когда расположенные на общей оси часовая, минутная и секундная стрелки правильно идущих часов образуют попарно углы в 120 3.66. Найдите все взаимно простые a и b, для которых a + b =.

a2 - ab + b2 3.67. Докажите, что если (a1, a2,..., an) = 1, то уравнение a1x1 + a2x2 +... + anxn = разрешимо в целых числах.

Определение. Пусть a1,..., an — отличные от 0 целые числа. Наименьшим общим кратным (НОК) этих чисел называется наименьшее положительное число, кратное всем этим числам. НОК чисел a1,...

..., an обозначается [a1,..., an].

3.68. Докажите равенства а) [1, 2,..., 2n] = [n, n + 1,..., 2n];

б) (a1, a2,..., an) = (a1, (a2,..., an));

в) [a1, a2,..., an] = [a1, [a2,..., an]].

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

а) Докажите, что можно провести только конечное число операций.

б) Финальный результат независимо от порядка действий будет одним и тем же. Например:

(4, 6, 9) (2, 12, 9) (2, 3, 36) (1, 6, 36), (4, 6, 9) (4, 3, 18) (1, 12, 18) (1, 6, 36).

3. Мультипликативные функции 3.70. Найдите наименьшее c, при котором а) уравнение 7x + 9y = c имело бы ровно 6 целых положительных решений;

б) уравнение 14x + 11y = c имело бы ровно 5 целых положительных решений.

3.71. В каких пределах должно заключаться c, чтобы уравнение 19x + 14y = c имело бы 6 целых положительных решений 3.72. Пусть a и b — натуральные взаимно простые числа. Рассмотрим точки плоскости с целыми координатами (x, y), лежащие в полосе 0 x b - 1. Каждой такой точке припишем целое число N(x, y) = = ax + by.

а) Докажите, что для каждого натурального c существует ровно одна точка (x, y) (0 x b - 1), что c = N(x, y).

б) Теорема Сильвестра. Докажите, что наибольшее c, для которого уравнение ax+by = c не имеет решений в целых неотрицательных числах, имеет вид c = ab - a - b.

3.73*. Пусть числа a и b взаимно просты. Докажите, что для того, чтобы уравнение ax + by = c имело ровно n целых положительных решений, значение c должно находиться в пределах (n - 1)ab + a + b c (n + 1)ab - a - b.

(См. также 1.48.) 3.74*. Отметим на прямой красным цветом все точки вида 81x + + 100y, где x, y — натуральные, и синим цветом — остальные целые точки. Найдите на прямой такую точку, что любые симметричные относительно нее целые точки закрашены в разные цвета. Объясните, почему такая точка существует.

3. Мультипликативные функции Основная теорема арифметики. Всякое натуральное число, большее 1, раскладывается и только одним способом (с точностью до порядка сомножителей) в произведение простых чисел.

3.75. Докажите основную теорему арифметики при помощи утверждения из задачи 3.38.

3.76. Найдите все двузначные числа, квадрат которых равен кубу суммы их цифр.

3.77. На какое количество нулей заканчивается число 100! 34 3. Алгоритм Евклида и основная теорема арифметики 3.78. Найдите наименьшее натуральное n, для которого 1999! не делится на 34n.

3.79. Докажите, что произведение чисел от n+1 до 2n делится на 2n, но не делится на 2n+1.

1 s s 3.80. Пусть a = p ·... · p, b = p ·... · p, где p1,..., ps — 1 s 1 s простые, и 1,..., s, 1,..., s 0. Докажите равенства:

s а) (a, b) = pmin(,1) ·... · pmin(,s);

1 s s б) [a, b] = pmax(,1) ·... · pmax(,s);

1 s в) (a, b)[a, b] = ab.

3.81. Докажите равенства:

а) [a, (a, b)] = a; в) abc = [a, b, c](ab, ac, bc);

б) (a, [a, b]) = a; г) abc = (a, b, c)[ab, bc, ac].

.

.

3.82. Докажите, что (bc, ac, ab). (a, b, c)2.

3.83. Приведите пример, когда равенство (a, b, c)[a, b, c] = abc не выполнено. Каким неравенством всегда будут связаны числа (a, b, c) [a, b, c] и abc 3.84. Сколько различных делителей имеют числа а) 2 · 3 · 5 · 7 · 11; б) 22 · 33 · 55 · 77 · 1111 3.85. Для каждого k от 1 до 6 найдите наименьшее натуральное число, которое имеет ровно k различных делителей.

3.86. Пусть (n) — количество положительных делителей натуральs ного числа n = p ·... · p, а (n) — их сумма. Докажите равенства:

1 s p1+1 - ps+1 - 1 s а) (n) = (1 + 1) ·... · (s + 1); б) (n) = ·... ·.

p1 - 1 ps - 3.87. Найдите натуральное число n, зная, что оно имеет два простых делителя и удовлетворяет условиям (n) = 6, (n) = 28.

3.88. Некоторое натуральное число n имеет два простых делителя.

Его квадрат имеет а) 15; б) 81 делителей. Сколько делителей имеет куб этого числа 3.89. Найдите натуральное число вида n = 2x · 3y · 5z, зная, что половина его имеет на 30 делителей меньше, треть — на 35 и пятая часть — на 42 делителя меньше, чем само число.

Определение. Функция f(n), определенная на множестве натуральных чисел называется мультипликативной, если она удовлетворяет двум условиям:

1) f(1) = 1; 2) f(m · n) = f(m) · f(n) при (m, n) = 1.

3. Мультипликативные функции Если f(1) = 1 и равенство f(m · n) = f(m) · f(n) выполнено для всех пар натуральных чисел m и n, то функция f(n) называется вполне мультипликативной.

3.90. Докажите мультипликативность функций (n) и (n).

3.91. Докажите неравенство (n) 2 n.

3.92. Пусть у двух целых положительных чисел равны суммы делителей и равны суммы всех обратных величин к делителям. Докажите, что эти числа равны.

3.93. Пусть (m, n) > 1. Что больше (m · n) или (m) · (n) Исследуйте тот же вопрос для функции (n). (См. также 4.144.) Определение. Число n называется совершенным, если (n) = 2n.

Например, числа 6 и 28 — совершенные:

1 + 2 + 3 + 6 = 2 · 6, 1 + 2 + 4 + 7 + 14 + 28 = 2 · 28.

3.94. Совершенные числа. Докажите, что если 2k - 1 = p — некоторое простое число Мерсенна, то n = 2k-1(2k - 1) — совершенное число.

3.95*. Теорема Эйлера. Докажите, что если n — четное совершенное число, то оно имеет вид n = 2k-1(2k - 1), и p = 2k - 1 — простое число Мерсенна.

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

Определение. Числа m и n называются дружественными, если сумма собственных делителей числа m равна n и, наоборот, сумма собственных делителей числа n равна m. Другими словами, числа m и n являются дружественными, если (m) - m = n, (n) - n = m, или (m) = m + n = (n).

3.96. Дружественные числа. Докажите, что если все три числа p = 3 · 2k-1 - 1, q = 3 · 2k - 1 и r = 9 · 22k-1 - 1 — простые, то числа m = 2k · p · q и n = 2k · r — дружественные. Постройте примеры дружественных чисел.

3.97. Может ли быть так, что а) (n) > 3n; б)* (n) > 100n 3.98. Задача Ферма. Найдите наименьшее число вида n = 2p1p2, где p1 и p2 — некоторые простые числа, такое, что (n) = 3n.

36 3. Алгоритм Евклида и основная теорема арифметики 3.99. Пусть — действительное положительное число, d — натуральное. Докажите, что количество натуральных чисел, не превосходящих и делящихся на d, равно.

d 3.100. Докажите, что для действительного положительного и на [] турального d всегда выполнено равенство =.

d d 3.101. Формула Лежандра. Число n! разложено в произведение s простых чисел n! = p... p. Докажите равенство 1 s n n n k = + + +...

pk p2 pk k 3.102. Докажите, что число p входит в разложение n! с показателем, n не превосходящим.

p - 3.103. Пусть представление числа n в двоичной системе выглядит следующим образом:

1 2 r n = 2e + 2e +... + 2e (e1 > e2 >... > er 0).

Докажите, что n! делится на 2n-r, но не делится на 2n-r+1.

3.104. Результат предыдущей задачи допускает обобщение. Пусть p — простое число и представление числа n в p-ичной системе имеет вид:

n = akpk + ak-1pk-1 +... + a1p1 + a0.

Найдите формулу, выражающую показатель p, с которым это число p входит в каноническое разложение n!, через n, p и коэффициенты ak.

3.105. При помощи формулы Лежандра из задачи 3.101 докажите, что число Cn (n 0) всегда целое. (См. также 2.115.) 2n n + (2m)! (2n)! 3.106. Докажите, что число (m, n 0) всегда целое.

m! n! (m + n)! n! 3.107. Существует ли такое целое r, что число является целым 2n-r при любом n 1 4. О том, как размножаются кролики Определение. Последовательность чисел Фибоначчи {F0, F1, F2,... } = {0, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610,... } задается условиями F0 = 0, F1 = 1, Fn+2 = Fn+1 + Fn (n 0).

4. О том, как размножаются кролики Эти числа были впервые описаны в «Книге абака» (1202 г.) итальянского математика Леонардо Пизанского (Фибоначчи).

3.108. Задача Леонардо Пизанского. Некто приобрел пару кроликов и поместил их в огороженный со всех сторон загон. Сколько кроликов будет через год, если считать, что каждый месяц пара дает в качестве приплода новую пару кроликов, которые со второго месяца жизни также начинают приносить приплод 3.109. О том, как прыгают кузнечики. Предположим, что имеется лента, разбитая на клетки и уходящая вправо до бесконечности. На первой клетке этой ленты сидит кузнечик. Из любой клетки кузнечик может перепрыгнуть либо на одну, либо на две клетки вправо. Сколькими способами кузнечик может добраться до n-й от начала ленты клетки (См. также 3.114.) 3.110. Некоторый алфавит состоит из 6 букв, которые для передачи по телеграфу кодированы так:

- - - - · - · · - - · - - · - - - - При передаче одного слова не сделали промежутков, отделяющих букву от буквы, так что получилась сплошная цепочка из точек и тире, содержащая 12 знаков. Сколькими способами можно прочитать переданное слово 3.111. Чему равны числа Фибоначчи с отрицательными номерами F-1, F-2,..., F-n,... 3.112. Тождество Кассини. Докажите равенство Fn+1Fn-1 - F2 = (-1)n (n > 0).

n Будет ли тождество Кассини справедливо для всех целых n (См.

также 12.13.) 3.113. Докажите следующие свойства чисел Фибоначчи:

а) F1 + F2 +... + Fn = Fn+2 - 1; в) F2 + F4 +... + F2n = F2n+1 - 1;

б) F1 + F3 +... + F2n-1 = F2n; г) F2 + F2 +... + F2 = FnFn+1.

1 2 n 3.114. Докажите, что при n 1 и m 0 выполняется равенство Fn+m = Fn-1Fm + FnFm+1.

Попробуйте доказать его двумя способами: при помощи метода математической индукции и при помощи интерпретации чисел Фибоначчи из задачи 3.109. Докажите также, что тождество Кассини является частным случаем этого равенства.

38 3. Алгоритм Евклида и основная теорема арифметики 3.115. Докажите равенства а) F2n+1 = F2 + F2 ;

n n+б) Fn+1Fn+2 - FnFn+3 = (-1)n+1;

в) F3n = F3 + F3 - F3.

n n+1 n-3.116. Вычислите F4 - FnFn+1Fn+3Fn+4.

n+3.117. Вычислите сумму 1 2 Fn + +... +.

1 · 2 1 · 3 Fn-1 · Fn+3.118. Делимость чисел Фибоначчи. Докажите справедливость следующих утверждений:

а) 2 | Fn 3 | n; в) 4 | Fn 6 | n;

б) 3 | Fn 4 | n; г) Fm | Fn m | n.

3.119. Докажите, что для любого натурального m существует число Фибоначчи Fn (n 1), кратное m.

3.120. Пусть первое число Фибоначчи, делящееся на m есть Fk.

Докажите, что m | Fn тогда и только тогда, когда k | n.

3.121. Докажите, что два соседних числа Фибоначчи Fn-1 и Fn (n 1) всегда взаимно просты.

3.122*. Теорема Люка. Докажите равенство (Fn, Fm) = F(m,n).

(См. также 3.141.) 3.123. В последовательности чисел Фибоначчи выбрано 8 чисел, идущих подряд. Докажите, что их сумма не является числом Фибоначчи.

3.124. Рассмотрим множество последовательностей длины n, состоящих из 0 и 1, в которых не бывает двух 1 стоящих рядом. Докажите, что количество таких последовательностей равно Fn+2. Найдите взаимно однозначное соответствие между такими последовательностями и маршрутами кузнечика из задачи 3.109.

3.125. Фибоначчиева система счисления. Докажите, что произвольное натуральное число n, не превосходящее Fm, единственным образом можно представить в виде m n = bkFk, k=где все числа b2,..., bm равны 0 либо 1, причем среди этих чисел нет двух единиц стоящих рядом, то есть bkbk+1 = 0 (2 k m - 1).

4. О том, как размножаются кролики Для записи числа в фибоначчиевой системе счисления используется обозначение:

n = (bk... b2)F.

(См. также 12.14, 4.193.) 3.126. Формула Бине. Докажите по индукции формулу Бине:

n - n Fn =, 1 + 5 1 - где = — «золотое сечение» или число Фидия, а = 2 («фи с крышкой») — сопряженное к нему. (См. также 11.43, 11.75.) 3.127. Докажите следующий вариант формулы Бине:

[(n-1)/2] 2n-1Fn = Cn 5k.

2k+k=(См. также 4.129.) 3.128. Докажите, что число Фибоначчи Fn совпадает с ближайшим n целым числом к, то есть n Fn = +.

3.129. Числа Фибоначчи и треугольник Паскаля. Докажите равенство:

C0 + C1 + C2 +... = Fn+1.

n n-1 n-Сумма, стоящая в левой части равенства, может быть интерпретирована, как сумма элементов треугольника Паскаля, стоящих в одной диагонали (См. приложение В, II и задачи 2.67, 3.124, 11.44 и 11.45.) 3.130. Вычислите сумму:

Sn = C0 - C1 + C2 -...

n n-1 n-(См. также 11.44, 11.45.) 3.131. Сколько существует последовательностей из 1 и 2, таких что сумма чисел в каждой такой последовательности равна n Например, если n = 4, то таких последовательностей пять:

11111, 112, 121, 211, 22.

3.132. Решите в целых числах уравнение x · n+1 + y · n = 1.

40 3. Алгоритм Евклида и основная теорема арифметики Определение. Последовательность чисел Люка {L0, L1, L2,... } = {2, 1, 3, 4, 7, 11, 18, 29, 47, 76, 123, 199, 322, 521,... } задается равенствами L0 = 2, L1 = 1, Ln+2 = Ln+1 + Ln (n 0).

3.133. Докажите, что числа Люка связаны с числами Фибоначчи соотношениями:

а) Ln = Fn-1 + Fn+1;

б) 5 Fn = Ln-1 + Ln+1;

в) F2n = Ln · Fn;

г) L2 + L2 = 5F2n+1;

n+1 n д) Fn+2 + Fn-2 = 3Fn.

(См. также 9.79, 11.41.) 3.134. В вершинах правильных многоугольников записываются числа 1 и 2. Сколько существует таких многоугольников, что сумма чисел стоящих в вершинах равна n (n 3) Две расстановки чисел, которые можно совместить поворотом не отождествляются.

3.135. Выразите Ln в замкнутой форме через и. (См. также 11.77.) 3.136. Докажите равенства 7 + 3 5 7 - 3 4 а) - = 1;

2 11 + 5 5 76 - 34 5 б) + = 1.

2 Найдите общую формулу, для которой данные равенства являются частными случаями.

3.137*. Решите в целых числах уравнения:

а) x2 - xy - y2 = 1;

б) x2 - xy - y2 = -1.

3.138. а) Докажите, что в последовательности чисел Фибоначчи при m 2 встречается не менее 4 и не более 5 m-значных чисел.

б) Докажите, что число F5t+2 (t 0) содержит в своей десятичной записи не менее t + 1 цифры.

3.139. Рассмотрим алгоритм Евклида из задачи 3.36 состоящий из k шагов. Докажите, что начальные числа m0 и m1 должны удовлетворять неравенствам m1 Fk+1, m0 Fk+2.

3.140. Теорема Ламе. Пусть число m1 в десятичной системе счисления записывается при помощи t цифр. Докажите, что при любом m5. Цепные дроби число шагов k в алгоритме Евклида для чисел m0 и m1 удовлетворяет неравенству k 5t.

3.141. Фибоначчиевы коэффициенты.

1 1 1 1 2 2 1 3 6 3 1 5 15 15 5 1 8 40 60 40 8 1 13 104 260 260 104 13 Данная таблица аналогична треугольнику Паскаля и состоит из фиk боначчиевых коэффициентов Fn, определяемых равенством Fn · Fn-1 ·... · Fn-k+k Fn = (0 k n).

Fk · Fk-1 ·... · Fа) Докажите, что фибоначчиевы коэффициенты обладают свойk k ством симметрии Fn = Fn-k.

k k-б) Найдите формулу, которая выражает коэффициент Fn через Fn-k и Fn-1 (аналогичную равенству б) из задачи 2.77).

в) Объясните, почему все фибоначчиевы коэффициенты являются целыми числами.

3.142*. Обобщенные биномиальные коэффициенты. Пусть A1, A2,... — последовательность ненулевых целых чисел, такая, что (Am, An) = A(m,n) (m, n 1).

Pages:     | 1 |   ...   | 2 | 3 || 5 | 6 |   ...   | 27 |






















© 2011 www.dissers.ru - «Бесплатная электронная библиотека»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.