ВУЗ:
Составители:
Рубрика:
36
нечётных чисел до 10 000 и последовательно просеивать их через этот мас-
сив, исключая большинство чисел после каждого прохода. Это потребует
просева приблизительно всего массива каждый раз (заметим, что с просты-
ми числами мы могли, по крайней мере, начинать с p
2
, где р было текущим
простым числом, используемым для просева). Лучше использовать два мас-
сива, из которых в первом находились бы числа, которые прошли просев, с
нулём в конце ряда чисел, который выполнял бы роль «часового», опреде-
ляя конец. Второй массив будет содержать только числа, которые остались
после просева, занимая место
в текущем проходе через первый массив. Та-
ким образом, числа записываются из первого массива во второй только, ес-
ли они сохранятся после отсева. Например, отсеивая по 3, в первом массиве
должны быть числа:
1, 3, 7, 9, 13, 15, 19, 21, 25, 27, 31, 33, 37, 39, 43, 45, . . .
Числа, записанные во второй массив тогда будут (просеивая по 7):
1, 3, 7, 9, 13, 15, 21, 25, 27, 31, 33, 37, 39, 43, 45, . .
Роль этих двух массивов тогда меняется, и на
следующем проходе
осуществляется просев по 9.
9. Сравнения
9.1. Упражнения
1. Приведите пример, показывающий, что если a ≡ b (mod m), тогда а
2
не обязательно будет сравнимо b
2
(mod m
2
). (Несмотря на то, что сравнение
должно сохраняться по m).
2. Покажите, что для некоторого целого числа a a
2
≡ 0 или 1 (mod 4).
Также покажите, что a
4
≡ 0 или 1 (mod 16). [Запишите a = 2k или 2k + 1.
В последнем случае полезно вспомнить, что k·(k + 1) всегда чётное число,
так как либо k, либо k + 1 будет чётным].
3. Докажите, что если число вида 16n + 15 представимо суммой a
1
4
+
+ a
2
4
+ . . . + a
r
4
целых чисел a
i
≥ 0 в четвёртой степени, тогда r ≥ 15.
(Общеизвестно, что любое целое число представимо суммой из 19 чи-
сел в четвёртой степени. Число 79, например, определённо нуждается
в 19 натуральных числах в четвёртой степени: 79 = 4 × 2
4
+ 15 × 1
4
, что яв-
ляется наиболее экономичным представлением).
4. Покажите, что для некоторого a a
2
≡ 0, 1 или 4 (mod 8). Докажите,
что число вида 8k + 7 не может быть представлено суммой трёх квадратов
от целых чисел ≥ 0.
5. Покажите, что если n – нечётное, то n
2
≡ 1 (mod 8). Покажите также,
что если 3 | n, тогда n
2
≡ 1 (mod 3). [Используйте представление n ≡ 1 или
2 (mod 3)]. Докажите, что если n – нечётное и не кратное 3, тогда
n
2
≡ 1 (mod 24). (В особенности это применимо к некоторому простому
числу n > 2). Из чего следует, что если n и m оба нечётные и не имеют дели-
теля 3, то 24 | (n
2
– m
2
)?
Страницы
- « первая
- ‹ предыдущая
- …
- 34
- 35
- 36
- 37
- 38
- …
- следующая ›
- последняя »
