Простые и составные числа. Как определить простое число или составное
Простые числа
Простые числа — это целые натуральные (положительные) числа больше единицы, которые имеют ровно 2 натуральных делителя (только 1 и самого себя), т.е. не делится ни на одно другое число, кроме самого себя и единицы. Все остальные числа кроме единицы называются составными. Таким образом, все натуральные числа, за исключением единицы, разбиваются на простые и составные.
Последовательность простых чисел начинается так (от 2 до 10000 их 1229):
2 3 5 7 11 13
17 19 23 29 31 37
41 43 47 53 59 61
67 71 73 79 83 89
97 101 103 107 109 113
127 131 137 139 149 151
157 163 167 173 179 181
191 193 197 199 211 223
227 229 233 239 241 251
257 263 269 271 277 281
283 293 307 311 313 317
331 337 347 349 353 359
367 373 379 383 389 397
401 409 419 421 431 433
439 443 449 457 461 463
467 479 487 491 499 503
509 521 523 541 547 557
563 569 571 577 587 593
599 601 607 613 617 619
631 641 643 647 653 659
661 673 677 683 691 701
709 719 727 733 739 743
751 757 761 769 773 787
797 809 811 821 823 827
829 839 853 857 859 863
877 881 883 887 907 911
919 929 937 941 947 953
967 971 977 983 991 997
1009 1013 1019 1021 1031 1033
1039 1049 1051 1061 1063 1069
1087 1091 1093 1097 1103 1109
1117 1123 1129 1151 1153 1163
1171 1181 1187 1193 1201 1213
1217 1223 1229 1231 1237 1249
1259 1277 1279 1283 1289 1291
1297 1301 1303 1307 1319 1321
1327 1361 1367 1373 1381 1399
1409 1423 1427 1429 1433 1439
1447 1451 1453 1459 1471 1481
1483 1487 1489 1493 1499 1511
1523 1531 1543 1549 1553 1559
1567 1571 1579 1583 1597 1601
1607 1609 1613 1619 1621 1627
1637 1657 1663 1667 1669 1693
1741 1747 1753 1759 1777 1783
1787 1789 1801 1811 1823 1831
1847 1861 1867 1871 1873 1877
1879 1889 1901 1907 1913 1931
1933 1949 1951 1973 1979 1987
1993 1997 1999 2003 2011 2017
2027 2029 2039 2053 2063 2069
2081 2083 2087 2089 2099 2111
2113 2129 2131 2137 2141 2143
2153 2161 2179 2203 2207 2213
2221 2237 2239 2243 2251 2267
2269 2273 2281 2287 2293 2297
2309 2311 2333 2339 2341 2347
2351 2357 2371 2377 2381 2383
2389 2393 2399 2411 2417 2423
2437 2441 2447 2459 2467 2473
2477 2503 2521 2531 2539 2543
2549 2551 2557 2579 2591 2593
2609 2617 2621 2633 2647 2657
2659 2663 2671 2677 2683 2687
2689 2693 2699 2707 2711 2713
2719 2729 2731 2741 2749 2753
2767 2777 2789 2791 2797 2801
2803 2819 2833 2837 2843 2851
2857 2861 2879 2887 2897 2903
2909 2917 2927 2939 2953 2957
2963 2969 2971 2999 3001 3011
3019 3023 3037 3041 3049 3061
3067 3079 3083 3089 3109 3119
3121 3137 3163 3167 3169 3181
3187 3191 3203 3209 3217 3221
3229 3251 3253 3257 3259 3271
3299 3301 3307 3313 3319 3323
3329 3331 3343 3347 3359 3361
3371 3373 3389 3391 3407 3413
3433 3449 3457 3461 3463 3467
3469 3491 3499 3511 3517 3527
3529 3533 3539 3541 3547 3557
3559 3571 3581 3583 3593 3607
3613 3617 3623 3631 3637 3643
3659 3671 3673 3677 3691 3697
3701 3709 3719 3727 3733 3739
3761 3767 3769 3779 3793 3797
3803 3821 3823 3833 3847 3851
3853 3863 3877 3881 3889 3907
3911 3917 3919 3923 3929 3931
3943 3947 3967 3989 4001 4003
4007 4013 4019 4021 4027 4049
4051 4057 4073 4079 4091 4093
4099 4111 4127 4129 4133 4139
4153 4157 4159 4177 4201 4211
4217 4219 4229 4231 4241 4243
4253 4259 4261 4271 4273 4283
4289 4297 4327 4337 4339 4349
4357 4363 4373 4391 4397 4409
4421 4423 4441 4447 4451 4457
4517 4519 4523 4547 4549 4561
4567 4583 4591 4597 4603 4621
4637 4639 4643 4649 4651 4657
4663 4673 4679 4691 4703 4721
4723 4729 4733 4751 4759 4783
4787 4789 4793 4799 4801 4813
4817 4831 4861 4871 4877 4889
4903 4909 4919 4931 4933 4937
4943 4951 4957 4967 4969 4973
4987 4993 4999 5003 5009 5011
5021 5023 5039 5051 5059 5077
5081 5087 5099 5101 5107 5113
5119 5147 5153 5167 5171 5179
5189 5197 5209 5227 5231 5233
5237 5261 5273 5279 5281 5297
5303 5309 5323 5333 5347 5351
5381 5387 5393 5399 5407 5413
5417 5419 5431 5437 5441 5443
5449 5471 5477 5479 5483 5501
5503 5507 5519 5521 5527 5531
5557 5563 5569 5573 5581 5591
5623 5639 5641 5647 5651 5653
5657 5659 5669 5683 5689 5693
5701 5711 5717 5737 5741 5743
5749 5779 5783 5791 5801 5807
5813 5821 5827 5839 5843 5849
5851 5857 5861 5867 5869 5879
5881 5897 5903 5923 5927 5939
5953 5981 5987 6007 6011 6029
6037 6043 6047 6053 6067 6073
6079 6089 6091 6101 6113 6121
6131 6133 6143 6151 6163 6173
6197 6199 6203 6211 6217 6221
6229 6247 6257 6263 6269 6271
6277 6287 6299 6301 6311 6317
6323 6329 6337 6343 6353 6359
6361 6367 6373 6379 6389 6397
6421 6427 6449 6451 6469 6473
6481 6491 6521 6529 6547 6551
6553 6563 6569 6571 6577 6581
6599 6607 6619 6637 6653 6659
6661 6673 6679 6689 6691 6701
6703 6709 6719 6733 6737 6761
6763 6779 6781 6791 6793 6803
6823 6827 6829 6833 6841 6857
6863 6869 6871 6883 6899 6907
6911 6917 6947 6949 6959 6961
6967 6971 6977 6983 6991 6997
7001 7013 7019 7027 7039 7043
7057 7069 7079 7103 7109 7121
7127 7129 7151 7159 7177 7187
7193 7207 7211 7213 7219 7229
7237 7243 7247 7253 7283 7297
7307 7309 7321 7331 7333 7349
7351 7369 7393 7411 7417 7433
7451 7457 7459 7477 7481 7487
7489 7499 7507 7517 7523 7529
7537 7541 7547 7549 7559 7561
7573 7577 7583 7589 7591 7603
7607 7621 7639 7643 7649 7669
7673 7681 7687 7691 7699 7703
7717 7723 7727 7741 7753 7757
7759 7789 7793 7817 7823 7829
7841 7853 7867 7873 7877 7879
7883 7901 7907 7919 7927 7933
7937 7949 7951 7963 7993 8009
8011 8017 8039 8053 8059 8069
8081 8087 8089 8093 8101 8111
8117 8123 8147 8161 8167 8171
8179 8191 8209 8219 8221 8231
8233 8237 8243 8263 8269 8273
8287 8291 8293 8297 8311 8317
8329 8353 8363 8369 8377 8387
8389 8419 8423 8429 8431 8443
8447 8461 8467 8501 8513 8521
8527 8537 8539 8543 8563 8573
8581 8597 8599 8609 8623 8627
8629 8641 8647 8663 8669 8677
8681 8689 8693 8699 8707 8713
8719 8731 8737 8741 8747 8753
8761 8779 8783 8803 8807 8819
8821 8831 8837 8839 8849 8861
8863 8867 8887 8893 8923 8929
8933 8941 8951 8963 8969 8971
8999 9001 9007 9011 9013 9029
9041 9043 9049 9059 9067 9091
9103 9109 9127 9133 9137 9151
9157 9161 9173 9181 9187 9199
9203 9209 9221 9227 9239 9241
9257 9277 9281 9283 9293 9311
9319 9323 9337 9341 9343 9349
9371 9377 9391 9397 9403 9413
9419 9421 9431 9433 9437 9439
9461 9463 9467 9473 9479 9491
9497 9511 9521 9533 9539 9547
9551 9587 9601 9613 9619 9623
9629 9631 9643 9649 9661 9677
9679 9689 9697 9719 9721 9733
9739 9743 9749 9767 9769 9781
9787 9791 9803 9811 9817 9829
9833 9839 9851 9857 9859 9871
9883 9887 9901 9907 9923 9929
9931 9941 9949 9967 9973
mirurokov.ru
Как найти простые числа? :: SYL.ru
Числа бывают разными: натуральными, естественными, рациональными, целыми и дробными, положительными и отрицательными, комплексными и простыми, нечетными и четными, действительными и др. Из данной статьи можно узнать, что такое простые числа.
Какие числа называют английским словом “симпл”?
Очень часто школьники на один из самых несложных на первый взгляд вопросов математики, о том что такое простое число, не знают, как ответить. Они часто путают простые числа с натуральными (то есть числа, которые используются людьми при счете предметов, при этом в некоторых источниках они начинаются с нуля, а в других - с единицы). Но это совершенно два разных понятия. Простые числа - это, натуральные, то есть целые и положительные числа, которые большее единицы и которые имеют всего лишь 2 натуральных делителя. При этом один из этих делителей - это данное число, а второй – единица. Например, три - это простое число, поскольку он не делится без остатка ни на какое другое число, кроме себя самого и единицы.
Составные числа
Противоположностью простых чисел являются составные. Они также являются натуральным, также больше единицы, но имеют не два, а большее количество делителей. Так, например, числа 4, 6, 8, 9 и т. д. являются натуральными, составными, но не простыми числами. Как видите – это в основном четные числа, но не все. А вот “двойка” – четное число и “первый номер” в ряду простых чисел.
Последовательность
Чтобы построить ряд простых чисел, необходимо совершить отбор из всех натуральных чисел с учетом их определения, то есть нужно действовать методом от противного. Необходимо рассмотреть каждое из натуральных положительных чисел на предмет того, имеет ли оно более двух делителей. Давайте постараемся построить ряд (последовательность), который составляют простые числа. Список начинается с двух, следующим идет три, поскольку оно делится только на себя и на единицу. Рассмотрим число четыре. Имеет ли оно делители, кроме четырех и единицы? Да, это число 2. Значит, четыре не является простым числом. Пять также является простым (оно, кроме 1 и 5, ни на какое другое число не делится), а вот шесть – делится. И вообще, если проследить за всеми четными числами, то можно заметить, что кроме “двух”, ни одно из них не является простым. Отсюда сделаем вывод, что четные числа, кроме двух, не являются простыми. Еще одно открытие: все числа, делящиеся на три, кроме самой тройки, будь то четные или нечетные, также не являются простыми (6, 9, 12, 15, 18, 21, 24, 27 и т.д.). То же самое касается и чисел, которые делятся на пять и на семь. Все их множество также не является простым. Давайте подведем итоги. Итак, к простым однозначным числам относятся все нечетные числа, кроме единицы и девятки, а из четных – только “два”. Сами десятки (10, 20,... 40 и др.) не являются простыми. Двузначные, трехзначные и т. д. простые числа можно определить, исходя из вышеизложенных принципов: если они не имеют других делителей, кроме их самих и единицы.
Теории о свойствах простых чисел
Существует наука, которая изучает свойства целых чисел, в том числе и простых. Это раздел математики, которая называется высшей. Помимо свойств целых чисел, она также занимается алгебраическими, трансцендентными числами, а также функциями различного происхождения, связанными с арифметикой этих чисел. В этих исследованиях, помимо элементарных и алгебраических методов, также используются аналитические и геометрические. Конкретно изучением простых чисел занимается “Теория чисел”.
Простые числа — “строительные блоки” натуральных чисел
В арифметике есть теорема, которая называется основной. Согласно ей, любое натуральное число, кроме единицы, можно представить в виде произведения, множителями которого являются простые числа, причем порядок следования множителей единственен, этот означает, что и способ представления единственен. Он называется разложением натурального числа на простые множители. Есть и другое название этого процесса – факторизация чисел. Исходя из этого, простые числа можно назвать “строительным материалом”, "блоками" для построения натуральных чисел.
Поиск простых чисел. Тесты простоты
Множество ученых разных времен пытались найти какие-то принципы (системы) для нахождения списка простых чисел. Науке известны системы, которые называются решето Аткина, решето Сундартама, решето Эратосфена. Однако они не дают каких-то существенных результатов, и для нахождения простых чисел используется простая проверка. Также математиками были созданы алгоритмы. Их принято называть тестами простоты. Например, существует тест, разработанный Рабином и Миллером. Его используют криптографы. Также существует тест Каяла-Агравала- Саскены. Однако он, несмотря на достаточную точность, очень сложен в вычислении, что принижает его прикладное значение.
Имеет ли множество простых чисел предел?
О том, что множество простых является бесконечностью, писал в книге “Начала” древнегреческий ученый Евклид. Он говорил так: “Давайте на минуту представим, что простые числа имеют предел. Тогда давайте перемножим их друг с другом, а к произведению прибавим единицу. Число, полученное в результате этих простых действий, не может делиться ни на одно из ряда простых чисел, потому что в остатке всегда будет единица. А это значит, что существует какое-то другое число, которое еще не включено в список простых чисел. Следовательно, наше допущение не верно, и это множество не может иметь предела. Помимо доказательства Евклида, существует более современная формула, данная швейцарским математиком восемнадцатого века Леонардом Эйлером. Согласно ему, сумма, обратная сумме первых n чисел растет неограниченно с ростом числа n. А вот формула теоремы относительно распределения простых чисел: (n) растёт, как n/ln (n).
Какое наибольшее простое число?
Все тот же Леонард Эйлер смог найти самое большое для своего времени простое число. Это 231 – 1 = 2147483647. Однако к 2013 году было вычислено другое наиболее точное самое большое в списке простых чисел – 257885161 – 1. Его называют числом Мерсенна. Оно содержит около 17 миллионов десятичных цифр. Как видите, число, найденное ученым из восемнадцатого века, в несколько раз меньше этого. Так и должно было быть, ведь Эйлер вел данный подсчет вручную, нашему же современнику наверняка помогала вычислительная машина. Более того, это число было получено на факультете математики в одном из американских факультетов. Числа, названные в честь этого ученого, проходят через тест простоты Люка-Лемера. Однако наука не желает останавливаться на достигнутом. Фонд Электронных рубежей, который был основан в 1990 году в Соединенных Штатах Америки (EFF), назначил за нахождение больших простых чисел денежную награду. И если до 2013 года приз полагался тем ученным, которые найдут их из числа 1 и 10 миллионов десятичных чисел, то сегодня это цифра достигла от 100 миллионов до 1 миллиарда. Размер призов составляет от 150 до 250 тысяч долларов США.
Названия специальных простых чисел
Те числа, которые были найдены благодаря алгоритмам, созданным теми или иными учеными, и прошли тест простоты, называются специальными. Вот некоторые из них:
1. Мерссена.
2. Вудаа.
3. Ферма.
4. Каллена.
5. Прота.
6. Миллса и др.
Простота этих чисел, названных в честь вышеперечисленных ученых, устанавливается с использованием следующих тестов:
1. Люка-Лемера.
2. Пепина.
3. Ризеля.
4. Биллхарта – Лемера – Селфриджа и др.
Современная наука не останавливается на достигнутом, и, вероятно, в ближайшем будущем мир узнает имена тех, кто смог получить приз в 250.000 долларов, найдя наибольшее простое число.
www.syl.ru
Простые числа | Математика
Определение
Натуральное число называется простым, если оно имеет только два делителя — единицу и само это число.
Примеры.
1) 5 — просто число, потому что оно делится только на 1 и на 5.
2) 11 — простое число. Его делители — 1 и 11.
3) 2 — простое число. Оно делится на 1 и на 2.
Обратите внимание, что 2 — единственное простое чётное число. Любое другое чётное число делится на 2, а значит, имеет более двух делителей и является составным.
Для удобства использования простые числа записывают в таблицу.
С помощью таблицы простых чисел можно быстро определить, является ли число простым или оно составное.
Таблица простых чисел до 997
www.for6cl.uznateshe.ru
Простые и составные числа
Определение 9.1. Натуральное число p называется простым, если оно имеет только два различных между собой натуральных делителя: 1 и p.
Примеры. 2, 3, 5, 7, 11, 13 – простые числа.
Определение 9. 2. Натуральное число, большее единицы, называется составным, если оно имеет более двух различных натуральных делителей.
Примеры. 4, 6, 8, 9, 10, 12 – составные числа.
Замечание 1. Из этих определений следует, что множество натуральных чисел можно разбить на три класса:
а) составные числа;
б) простые числа;
в) единица.
Если а – составное, то а = nq, где 1 < n < a, 1 < q < a.
Простейшие свойства простых чисел
10. Если а 
Z и p – простое, то (а, p) = 1 
а p.
Действительно, пусть d = (a, p), тогда (а d) 
p d, т.к. p – простое число, то оно имеет два делителя 1 и p. Если (а, p) = 1, то а и p взаимно просты, а если (а, p) = p, то а p.
20. Если произведение нескольких сомножителей делится на p, то, по крайней мере, один из сомножителей делится на p.
Действительно, пусть произведение а1 ∙ а2 ∙ … ∙ аn делится на p. Если предположить противное: все аi не делятся на p, то (а1 ∙ а2 ∙ … ∙ аn, p) = 1, следовательно, какой-то сомножитель делится на p.
30. Различные простые числа взаимно просты.
40. Наименьший простой делитель p натурального числа n > 1 не превосходит 
.
Пусть n = p ∙ n1, причем p 
n1 и p – простое. Тогда n 
p2
p 
.
50. Если натуральное число n не делится ни на одно простое число p , тоn – простое, в противном случае оно будет составным.
Данное свойство непосредственно следует из свойства 40.
Пример. Выясним, будет ли число 157 простым?
Выпишем простые делители, не превосходящие 
: 2, 3, 5, 7, 11. Проверяем, что 157 не делится на 2, на 3, на 5, на 7, на 11. Следовательно, число 157 – простое.
Решето Эратосфена
На свойстве 50 основан метод, позволяющий определить список простых чисел p1 < p2 < … до заданной границы n. Этот метод носит название решето Эратосфена, названный в честь древнегреческого математика, географа и астронома.
Шаг 1. Выпишем подряд все натуральные числа 2, … , n – 1, n.
Положим, что p1 = 2 и вычеркнем все последующие числа, делящиеся на 2, кроме p1 = 2.
Шаг 2. Пусть k 
2 и уже определены числа p1,…, pk-1. Обозначим pk первое невычеркнутое число, следующее за pk-1. Если pk2 > n, то обозначим pk+1, pk+2, … все оставшиеся невычеркнутыми числа, следующие за pk, в порядке возрастания. На этом алгоритм завершает свою работу.
Шаг 3. Если pk2
n, то вычеркиваем числа, делящиеся на pk, начиная с pk2 (двигаясь до n с шагом pk). Вычеркнутые ранее числа также принимаются в учет, но не вычеркиваются еще раз. По завершении процедуры алгоритм увеличивает индекс k на единицу и переходит к шагу 2.
В результате алгоритм оставляет невычеркнутыми только простые числа.
Примеры: 1. Найти все простые числа, меньшие 30.
Применим решето Эратосфена, остановившись, как только найдём простое число, не меньшее 
=5,… , т.е. простое число 7.
Теорема Евклида. Основная теорема арифметики
Теорема 9.1 (теорема Евклида). Множество простых чисел бесконечно.
Доказательство.
Предположим противное, пусть p1, p2, … , pk – все простые числа, где p1 = 2, а pk – самое большое простое число.
Составим натуральное число n = p1 · p2 · … · pk + 1, т.к. n > pi, то оно должно быть составным. Покажем, что наименьший делитель q
1 числа n будет простым. Так как n – составное, то n = n1 ∙ q, где q < n1. Если предположить, что q – составное число, то q = q1 ∙ k и n = n1 ∙ q1 ∙ k, так как q1 < q, то q – уже не будет наименьшим делителем числа n, что противоречит условию. Итак, наименьший делитель числа n будет простым. Однако n не делится ни на p1, ни на p2, … , ни на pk, так как 1 не делится на любое pi .
Следовательно, наше предположение о конечности множества простых чисел было неверно.
Замечание 2. Простые числа составляют лишь небольшую часть чисел натурального ряда. Доказано, что в натуральном ряду существуют сколь угодно длинные интервалы, не содержащие ни одного простого числа.
Теорема 9. 2 (основная теорема арифметики). Любое натуральное число n > 1 может быть представлено единственным образом в виде произведения простых чисел, с точностью до порядка сомножителей.
Доказательство.
I. Докажем возможность представления методом математической индукции по величине числа. Пусть n 
N и n > 1.
1) n = 2. Утверждение выполняется, так как 2 – простое число.
2) Предположим, что утверждение теоремы выполнено для всех натуральных чисел,меньших числа k.
3) Покажем, что утверждение выполнено для k.
а) Если k – простое число, то доказывать нечего.
б) Если k – составное число, то оно имеет делитель а, такой, что 1 < a < k . Тогда k = a ∙ b. Очевидно, что 1 < b < k. Согласно предположению, теорема выполнена для чисел а и b, т. е. а = p1 ∙ p2 ∙ … ∙ ps и b = q1 ∙ q2 ∙ … ∙ qm, где pi, qj – простые. Тогда k = p1 ∙ p2 ∙ … ∙ ps ∙ q1 ∙ q2 ∙ … ∙ qm. Полученная формула означает, что существует представление числа k в виде произведения простых чисел.
Согласно принципа математической индукции возможность представления в виде произведения простых чисел доказана для любого натурального n > 1.
II. Покажем, что представление числа n в виде произведения простых чисел единственно с точностью до порядка сомножителей.
Пусть n = p1 ∙ p2 ∙ … ∙ ps и n = q1 ∙ q2 ∙ … ∙ qr, где pi, qj – простые числа, тогда будет иметь место равенство:
p1 ∙( p2 ∙ … ∙ ps) = q1 ∙ q2 ∙ … ∙ qr(1)
Тогда простое число p1 делит q1 ∙ q2 ∙ … ∙ qr, так что p1 делит одно из простых чисел правой части, пусть q1p1 , а значит, p1 = q1 . Поэтому обе части рассматриваемого равенства можно сократить на p1. Разделив обе части равенства (1) на p1, получим равенство p2 ∙ … ∙ ps= q2 ∙ … ∙ qr . Повторяя процесс рассуждения еще (s – 1) раз, мы получим равенство:
1 = qs+1 ∙ qs+2 ∙ …∙ qr
Так как все qi > 1, то это равенство невозможно. Следовательно, в обеих разложениях число сомножителей одинаково (s = r) и сами сомножители одинаковы.
Замечание 3. В разложении числа n на простые сомножители некоторые из них могут повторяться. Обозначим буквами кратность их вхождения вn, получим так называемое каноническое разложение числа n:
МЕТОДИКА 19. Тема: Простые числа, их свойства. Основная теорема арифметики.
I.Основные понятия: простые числа, составные числа, основная теорема арифметики.
Ранее изученный материал: делители и кратные, признаки делимости.
Теоретический материал темы:
Натуральное число называют простым, если оно имеет только два делителя: единицу и само это число. Натуральное число называют составным, если оно имеет более двух делителей.
Свойства простых чисел:
10. Любое натуральное число либо делится на простое, либо взаимно просто с ним.
20. Произведение натуральных чисел делится на простое тогда и только тогда, когда хотя бы одно из них делится на это простое.
30. Простых чисел бесконечно много (нет самого большого простого числа).
40. Если натуральное число не делится ни на одно простое, квадрат которого не превосходит это натуральное число, то оно само простое.
50. Любое простое число p(p > 3) представимо в виде .
Основная теорема арифметики: всякое составное число можно разложить на простые множители. При любом способе получается одно и то же разложение, если не учитывать порядка записи множителей.
studfiles.net
Содержание
Инструкция
|
completerepair.ru
