Простое искусство
Всем нам знакомы простые числа, вот они слева направо: 2, 3, 5, 7, 11, 13, и так далее. И чем дальше, тем реже в ряду натуральных чисел попадаются простые — например, среди первой сотни есть 25 простых чисел, а между 10 000 и 10 100 простых уже всего шесть: 10 003, 10 019, 10 043, 10 049, 10 057 и 10 069.
Тем не менее, доля простых убывает достаточно медленно: среди n-значных чисел простых примерно одно из каждых 2,3n. И это непраздное знание: для известного алгоритма шифрования RSA необходимо выбрать два простых числа, которые нельзя было бы подобрать перебором. Обычно это делают, перебирая случайно взятые числа из сотен десятичных знаков, пока не наткнутся на простое (и исключая «слишком специальные» числа). Но нужно еще проверить число на простоту!
Относительно большая доля простых чисел означает также, что у конкретного большого числа, скорее всего, можно просто подкрутить несколько цифр — и получить простое.
Самый знаменитый (и, видимо, самый первый) пример такой картины — это простое число, изображающее герб Тринити Холла, одного из старейших колледжей Кембриджа, среди выпускников которого, например, Стивен Хокинг. Его в свое время обнаружил математик Джеймс Макки (James McKee), оно состоит из 1350 цифр (это год основания колледжа), и выглядит вот так.
С ростом вычислительной мощности компьютеров и упрощения доступа к библиотекам для работы с большими числами создавать такие изображения стало проще. Вот примеры:
В работе Закари Абеля (Zachary Abel) есть потрет Софи Жермен, полученный закрашиванием простого числа Софи Жермен (таким простым p, что 2p + 1 тоже простое).
А если сопоставить с цифрами цветовую палитру, можно найти простое число, которое будет выглядеть, как «Звездная ночь» или «Большая волна в Канагаве».
Самое сложное при работе с такими картинками — это, собственно, проверка найденных чисел на простоту.
Как проверить на простоту 200-значное число N? О том, чтобы перебрать все возможные делители от единицы до 100-значного корня из N, не может быть и речи: даже если бы Земля состояла только из современных компьютеров, занятых только этой задачей, это все равно потребовало бы больше времени, чем прошло с момента Большого Взрыва.
Поэтому проверка на простоту больших чисел опирается на более сложные признаки. Одним из таких признаков является Малая теорема Ферма: если N простое, то для любого b его степень bN дает при делении на N тот же остаток, что и само b. Например, число 11 простое, и 211 = 2048 при делении на 11 дает остаток 2.
Поэтому, если для какого-то b разница bN — b не делится на N, то это гарантирует, что N составное (то есть не простое). Можно сказать, что число b выступает неопровержимым свидетелем не-простоты N.
А что, если различные b — например, выбираемые случайно, — раз за разом отказываются свидетельствовать о не-простоте N? Можно ли отсюда сделать вывод, что N простое? Увы — нет. Есть и составные числа N, для которых bN — b всегда делится на N. Такие числа называют числами Кармайкла; первые из них это:
- 561 = 3 × 11 × 17,
- 1105 = 5 × 13 × 17,
- 1729 = 7 × 13 × 19.
Другой признак, тоже неопровержимо свидетельствующий о том, что число N составное — это наличие «лишнего» корня у квадратного уравнения. Например, если у уравнения x2 = 1 по модулю N есть решение x, не сравнимое ни с 1, ни с (-1), то N точно составное. Действительно, x2 — 1 = (x — 1)(x + 1) делится на N, и если бы N было простым, то на него делился бы хотя бы один из сомножителей. Но как такой лишний квадратный корень найти?
Можно скрестить поиск корня из единицы с малой теоремой Ферма, получив достаточно надежный (хоть и вероятностный) тест Миллера-Рабина.
d × m = bN — 1
можно посмотреть на последний не-единичный элемент (если такой есть). И если это не (-1) по модулю N, то N — составное.
И наконец, если b от 2 до N — 1 взять случайным — то шанс, что (любое) составное
Кстати — при некоторых, довольно правдоподобных, предположениях (если справедлива обобщенная гипотеза Римана), тест Миллера-Рабина можно сделать и детерминированным — оказывается, что достаточно проверить все не слишком большие остатки b. А то, что n-значное число можно проверить на простоту за полиномиальное по количеству знаков время без дополнительных предположений, было доказано уже в нашем тысячелетии.
И напоследок — еще одно простое число, десятичная запись которого состоит из нулей и единиц:
3-8Радикалы.
Рациональные и иррациональные числа. Вещественные числа. Навыки
в
A L G E B R A
Содержание | Главная
26
Квадратные числа
Знак корня и подкоренное число
Рациональные и иррациональные числа
Какие квадратные корни рациональны?
Уравнение x ² = a и главный квадратный корень
2-й уровень :
Уравнения ( x + a )² = b
Определение квадратного корня
Рационализация знаменателя
Действительные числа
ВОТ ПЕРВЫЕ ДЕСЯТЬ квадратных чисел и их корни:
| Квадратные числа | 1 | 4 | 9 | 16 | 25 | 36 | 49 | 64 | 81 | 100 |
| Квадратный корень | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
= 5.
«Квадратный корень из 25 равен 5.»
Этот знак называется подкоренным знаком (от латинского основания = корень). Число под радикалом называется подкоренным. В примере 25 — это подкоренное число.
Проблема 1. Оцените следующее.
Чтобы увидеть ответ, наведите указатель мыши на цветную область.
Чтобы снова закрыть ответ, нажмите «Обновить» («Reload»).
Сначала решай задачу сам!
| а) | = 8 | б) | = 12 | в) | = 20 | |||||
| г) | = 17 | д) | = 1 | е) | = | 7 9 | ||||
Пример 1. Вычислить .
Раствор . = 13.
Для 13 · 13 — квадратное число.
И квадратный корень из 13 · 13 равен 13,9.0907
Если a — любое целое число, то a · a — квадратное число, а
Проблема 2. Оцените следующее.
| а) | = 28, | б) | = 135, |
| в) | = 2 · 3 · 5 = 30. |
У нас есть следующая теорема:
Квадратное число, умноженное на квадратное число, само по себе является квадратным числом.
Например,
36 · 81 = 6 · 6 · 9 · 9 = 6 ·
9 · 6 · 9= 54 · 54Задача 3. Без умножения данных квадратных чисел каждое произведение квадратных чисел равно какому квадратному числу?
а) 25 · 64 = 5 · 8 · 5 · 8 = 40 · 40
б) 16 · 49 = 4 · 7 · 4 · 7 = 28 · 28
в) 4 · 9 · 25 = 2 · 3 · 5 · 2 · 3 · 5 = 30 · 9 070
Рациональные и иррациональные числа
Рациональное число — это любое арифметическое число: любое целое число, дробь, смешанное число или десятичное число; вместе с его отрицательным образом.
Рациональное число имеет то же отношение к 1, что и два натуральных числа.
Вот что значит рациональное число . Что касается того, как это выглядит, то оно может принимать форму дроби, где
Задача 4. Какие из следующих чисел являются рациональными?
| 1 | −6 | 3½ | 4 5 | − | 13 5 | 0 | 7.38609 |
Все они.
В этот момент учащийся может задаться вопросом: какое число не является рациональным?
Примером такого числа является («Квадратный корень из 2»). это не арифметическое число. близко, потому что
| 7 5 | · | 7 5 | = | 49 25 |
— что почти 2.
Чтобы увидеть, что не существует рационального числа, квадрат которого равен 2, предположим, что они были. Понятно, что это не целое число. Он будет в виде дроби в низших выражениях. Но квадрат дроби в наименьших терминах также и в наименьших терминах.
Никаких новых множителей не вводится, и знаменатель никогда не делится на числитель, чтобы получить 2 или любое целое число.
Не существует рационального числа, квадрат которого равен 2, или числа, не являющегося полным квадратом. Поэтому мы говорим, что это иррациональное число.
В десятичном приближении
1,414
(Волнистый знак равенства означает «приблизительно».)
Откуда мы могли это знать? Умножив 1,414 само на себя. Если мы это сделаем, то получим 1,999396, что почти равно 2. Но должно быть ясно, что никакое десятичное число, умноженное само на себя, никогда не может быть точно 2,0000000000000000000. Если десятичная дробь оканчивается на 1, то ее квадрат будет заканчиваться на 1.
Если десятичная дробь оканчивается на 2, ее квадрат оканчивается на 4. И так далее. Никакое десятичное число — никакое арифметическое число — умноженное само на себя никогда не даст 2.
иррационально.
Вопрос. Квадратные корни каких натуральных чисел являются рациональными?
Ответ. Только квадратные корни из квадратных чисел .
= 1 рациональный
Иррациональный
Иррациональный
= 2 Рациональное
, , , Иррациональный
= 3 Рациональное
И так далее.
Задача 5. Назовите имя каждого числа.
| а) | Квадратный корень из 3. | б) | Квадратный корень из 8. | в) | 3. |
| г) | 2 5 | д) | Квадратный корень из 10 |
Задача 6.
Какие из следующих чисел рациональные, а какие иррациональные?
а) Иррациональный б) Рациональный
в) Рациональное d) Иррациональное
Только рациональное число мы можем точно знать и назвать. Иррациональное число мы можем знать только как рациональное приближение.
О десятичном представлении как иррациональных, так и рациональных чисел см. Тему 2 Precalculus.
Уравнение x ² = a и главный квадратный корень
Пример 2. Решите уравнение:
.| х ² | = | 25. | |
| Решение . | х | = | 5 или -5, потому что (-5)² = 25. |
| Другими словами, | |||
| х | = | или –. | |
Однако мы говорим, что положительное значение, 5, является главным квадратным корнем. То есть мы говорим, что «квадратный корень из 25» равен 5,9.0907
= 5.
Что касается -5, то это «минус квадратного корня из 25».
— = -5.
Таким образом, символ относится к одному неотрицательному числу.
Пример 3. Решите это уравнение:
.| х ² | = | 10. | |
| Решение . | х | = | или –. |
Всегда, если уравнение выглядит так,
| х ² | = | и , | ||
| тогда решение будет выглядеть так: | ||||
| х | = | или –. | ||