Н. Макарова

 

П Р О С Т Ы Е    Ч И С Л А

 

В этой статье хочу представить ещё одну главу из рукописи моей книги “Компьютер решает головоломки”. Одна из представленных глав – “Магические квадраты” (http://www.klassikpoez.narod.ru/magich.htm ). Эта глава впоследствии выросла в большую книгу “Волшебный мир магических квадратов”. Читайте эту книгу (http://www.klassikpoez.narod.ru/glavnaja.htm )!

 

Конечно, сделаны некоторые дополнения к тому, что есть в рукописи, потому что книга была написана 17 лет назад, а с тех пор появилось много нового в этой области. В то же время хочу заметить, что всё это время ничуть не следила за новыми результатами, поэтому прошу не сетовать на пробелы, связанные с этим отставанием. Моя статья не претендует на научность и не представляет полные и исчерпывающие факты по теме. Цель статьи в популярной форме рассказать о простых числах тем, кто впервые знакомится с данным понятием.

 

Сразу замечу, что простые числа принадлежат множеству натуральных чисел. Евклид определял простые числа так: “Простое число есть измеряемое только единицей”. Иными словами, простые числа не имеют других делителей, кроме единицы и самого себя. Если p простое число, то его можно представить в виде произведения двух натуральных чисел только следующим образом: p = p*1. Числа, не являющиеся простыми, называются составными. Понятно, что всякое составное число имеет не меньше двух делителей отличных от 1. Кроме того, любое составное число N можно представить в виде следующего произведения:

 

N = p1q1 * p2q2 * … * pmqm, где piпростые числа, m ≥ 1, qi ≥ 1 (при m = 1 q1 > 1, при qi =1 m > 1).

 

Таким образом, простые числа – это как бы “кирпичики” для строительства всех натуральных чисел. Например, число N = 500 представимо в виде такого произведения:

 

N = 22 * 53

 

Представление составного числа в указанном виде называют разложением числа на простые множители. Все, наверное, хорошо помнят эту процедуру, с которой познакомились ещё на уроках арифметики. Помню, мы делали это так:

 

500

2

250

2

125

5

25

5

5

5

1

 

 

Деление производится до тех пор, пока слева не получается частное, равное 1; справа находятся простые множители, на которые разложено данное составное число. Однако не всегда так просто разложить заданное число на простые множители. Попробуйте-ка разложить на простые множители число N = 13593. Конечно, очевидно, что это число делится на 3, потому что сумма цифр числа делится на 3. Разделив число на 3, получаем число 4531. Это число не делится ни на 2, ни на 3, ни на 5, ни на 7. Итак, пока вы не дойдёте до первого простого числа, на которое полученное число делится, вы не продвинетесь ни на йоту в разложении этого числа на простые множители.

При разложении составного числа на простые множители используются признаки делимости. Признаки делимости на 2, 3 и 5 очень простые. Число делится: а) на 2 тогда и только тогда, когда его последняя цифра чётная; б) на 3 тогда и только тогда, когда сумма цифр этого числа делится на 3; в) на 5 тогда и только тогда, когда его последняя цифра 0 или 5. Признак делимости на 11: надо присвоить цифрам числа, начиная справа, попеременно знак “плюс” и знак “минус”, последняя цифра берётся со знаком “плюс”; затем сложить полученные значения. Исходное число делится на 11 тогда и только тогда, когда полученная сумма делится на 11. Пусть, например, надо определить, делится ли на 11 число 14399. Составляем сумму: 9 + (-9) + 3 + (-4) + 1 = 0. Полученная сумма делится на 11, следовательно, данное число тоже делится на 11. Так, можно сразу сказать, что любое число, составленное из чётного количества единиц (например: 1111, 11111111) делится на 11, а всякое число, составленное из нечётного количества единиц (например: 111, 1111111) не делится на 11. Точно так же можно определить, делится ли на 11, любое число, составленное другой цифрой, например: 3333333, 8888.

Признаков делимости на 7 существует несколько, но в [2] отмечается, что все они требуют не меньше затрат времени, чем обычное деление числа на 7. Это значит, что проще поделить число на 7 обычным образом, чем применять признак делимости. Подробнее о признаках делимости можно прочитать в [2].

 

Число 1 не относится к простым числам. “Математики предпочитают не считать 1 простым числом, поскольку в таком случае многие важные теоремы формулируются проще. Например, «основная теорема теории чисел» утверждает, что любое целое число допускает однозначное (с точностью до порядка множителей) разложение на простые множители. Так число 100 представимо в виде произведения четырёх простых множителей 2*2*5*5. Всякий другой набор (отличающийся хотя бы одним числом) простых множителей не даст в произведении числа 100. Если же считать единицу простым числом, то эта весьма важная теорема неверна: число 100 в этом случае представимо в виде произведения бесконечно многих различных наборов простых чисел, например, в виде 2*2*5*5*1*1”. [2]

 

Единственное чётное простое число 2. Все остальные простые числа нечётные, то есть любое простое число, отличное от 2, можно записать в виде: p = 2k + 1 (k ≥ 1).

Как уже сказано, множество простых чисел является подмножеством множества натуральных чисел. Как и множество натуральных чисел, множество простых чисел бесконечно. Это доказал Евклид. Приведу здесь доказательство этого утверждения, взятое в [3]. Положим, что ряд простых чисел ограничен и исчерпывается числами 2, 3, 5, …, p; в таком случае число N = (2*3*5* … *p) + 1, очевидно, не делится ни на 2, ни на 3, … ни на p, так как при делении на каждое из этих чисел мы получаем в остатке единицу. Поэтому должно иметь место одно из двух: либо это есть простое число, либо существуют простые числа, отличные от 2, 3, …, p. Но то и другое противоречит нашему предположению, и теорема, таким образом, доказана.

 

Для начала приведу ряд простых чисел в интервале (1, 500). Cделаю это в форме таблицы, чтобы лучше увидеть, как распределяются простые числа в  ряду натуральных чисел (рис. 1). Ячейки, содержащие простые числа, выделены оранжевым цветом.

 

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

72

73

74

75

76

77

78

79

80

81

82

83

84

85

86

87

88

89

90

91

92

93

94

95

96

97

98

99

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

199

200

201

202

203

204

205

206

207

208

209

210

211

212

213

214

215

216

217

218

219

220

221

222

223

224

225

226

227

228

229

230

231

232

233

234

235

236

237

238

239

240

241

242

243

244

245

246

247

248

249

250

251

252

253

254

255

256

257

258

259

260

261

262

263

264

265

266

267

268

269

270

271

272

273

274

275

276

277

278

279

280

281

282

283

284

285

286

287

288

289

290

291

292

293

294

295

296

297

298

299

300

301

302

303

304

305

306

307

308

309

310

311

312

313

314

315

316

317

318

319

320

321

322

323

324

325

326

327

328

329

330

331

332

333

334

335

336

337

338

339

340

341

342

343

344

345

346

347

348

349

350

351

352

353

354

355

356

357

358

359

360

361

362

363

364

365

366

367

368

369

370

371

372

373

374

375

376

377

378

379

380

381

382

383

384

385

386

387

388

389

390

391

392

393

394

395

396

397

398

399

400

401

402

403

404

405

406

407

408

409

410

411

412

413

414

415

416

417

418

419

420

421

422

423

424

425

426

427

428

429

430

431

432

433

434

435

436

437

438

439

440

441

442

443

444

445

446

447

448

449

450

451

452

453

454

455

456

457

458

459

460

461

462

463

464

465

466

467

468

469

470

471

472

473

474

475

476

477

478

479

480

481

482

483

484

485

486

487

488

489

490

491

492

493

494

495

496

497

498

499

500

 

Рис. 1

 

Вот так причудливо располагаются простые числа в ряду натуральных чисел! Обратите внимание на простые числа, которые находятся рядом, например: 2 и 3; 5 и 7; 11 и 13; 17 и 19 и т. д. Такие пары простых чисел называются близнецами. До сих пор неизвестно, конечно или бесконечно число пар близнецов. Однако, ясно, что по мере возрастания чисел близнецы встречаются всё реже и реже.

 

Плотность распределения простых чисел среди натурального ряда различна, есть участки, где простые числа располагаются гуще. Вместе с тем, существуют целые оазисы, не содержащие ни одного простого числа. Справедливо следующее утверждение:

 

Т Е О Р Е М А   1

 

Для любого натурального k можно указать ряд из k последовательных натуральных чисел, в котором нет ни одного простого числа.

 

 

Предлагаю читателям доказать эту теорему.

 

Основная трудность в нахождении всех простых чисел состоит в том, что математикам не удаётся установить закон распределения простых чисел. Количество простых чисел, не превосходящих N, обозначается π(N). Около 1800 г. два математика (А. Лежандр и К. Гаусс) независимо друг от друга высказали гипотезу, согласно которой

 

π(N)N/lnN

 

и что данное приближение тем лучше, чем больше N. Эта гипотеза впоследствии получила название теоремы об асимптотическом распределении простых чисел и была строго доказана в 1896 г. [2]

Например, количество простых чисел, не превосходящих 1000, оценивается числом 1000/ln1000, что примерно равно 145. Точное значение количества простых чисел, не превосходящих 1000, π(1000) = 168.

Величина π(N)/N называется средней плотностью простых чисел среди первых N натуральных чисел. Изучение таблиц простых чисел показывает, что с ростом N простые числа встречаются в среднем всё реже. Эйлер доказал, что lim (π(N)/N) = 0 при N стремящемся к бесконечности. Отсюда, в частности, следует, что простые числа в среднем располагаются реже, чем члены какой угодно арифметической прогрессии. Можно доказать, что простые числа располагаются всё же гуще квадратов натуральных чисел.

В 1837 г. немецкий математик Л. Дирихле доказал, что в любой арифметической прогрессии, первый член и разность которой взаимно просты (определение взаимно простых чисел см. далее), есть бесконечно много простых чисел.

В 1852 г. П. Л. Чебышев доказал предположение французского математика Ж. Бертрана о том, что для любого натурального числа N между числами N и 2N всегда есть простое число. [5]

 

 

Леонард   Эйлер (1707 – 1783)

 

Примечание: портрет Леонарда Эйлера из [6].

 

Самый знаменитый квадратичный трёхчлен Л. Эйлера, производящий простые числа:

 

x2 + x + 41

 

Первые 40 значений этого трёхчлена (при x = 0, 1, 2, …, 39) являются простыми числами.

Из 2398 первых значений, принимаемых этим трёхчленом, ровно половина - простые числа. Перебрав все значения знаменитого трёхчлена, не превышающие 10 000 000, Улам, Стейн и Уэллс обнаружили, что доля простых чисел среди них составляет 0, 475… . [2]

Составив программку вычисления значений данного трёхчлена Эйлера, я получила 200 первых значений (x принимает значения от 0 до 199). Вот они:

 

41 43  47  53  61  71  83  97  113  131  151  173  197  223  251  281  313  347  383  421  461  503  547  593  641  691  743  797  853  911  971  1033  1097  1163  1231  1301  1373  1447  1523  1601  1681  1763  1847  1933  2021  2111  2203  2297  2393  2491  2591  2693  2797  2903  3011  3121  3233  3347  3463  3581  3701  3823  3947  4073  4201  4331  4463  4597  4733  4871  5011  5153  5297  5443  5591  5741  5893  6047  6203  6361  6521  6683  6847  7013  7181  7351  7523  7697  7873  8051  8231  8413  8597  8783  8971  9161  9353  9547  9743  9941  10141  10343  10547  10753  10961  11171  11383  11597  11813  12031  12251  12473  12697  12923  13151  13381  13613  13847  14083  14321  14561  14803  15047  15293  15541  15791  16043  16297  16553  16811  17071  17333  17597  17863  18131  18401  18673  18947  19223  19501  19781  20063  20347  20633  20921  21211  21503  21797  22093  22391  22691  22993  23297  23603  23911  24221  24533  24847  25163  25481  25801  26123  26447  26773  27101  27431  27763  28097  28433  28771  29111  29453  29797  30143  30491  30841  31193  31547  31903  32261  32621  32983  33347  33713  34081  34451  34823  35197  35573  35951  36331  36713  37097  37483  37871  38261  38653  39047  39443  39841

 

                        Предлагаю читателям найти среди этих значений простые числа, не считая первые 40, выделенные красным цветом.

Впоследствии подобные трёхчлены получили название “генераторы простых чисел” [7].

Покажу спираль Улама (рис. 1а), начинающуюся с числа 41 (о спирали Улама см. в [2]).

 

1640

1639

1638

1637

1636

1635

1634

1633

1632

1631

1630

1629

1628

1627

1626

1625

1624

1623

1622

1621

1620

1619

1618

1617

1616

1615

1614

1613

1612

1611

1610

1609

1608

1607

1606

1605

1604

1603

1602

1601

1485

1484

1483

1482

1481

1480

1479

1478

1477

1476

1475

1474

1473

1472

1471

1470

1469

1468

1467

1466

1465

1464

1463

1462

1461

1460

1459

1458

1457

1456

1455

1454

1453

1452

1451

1450

1449

1448

1447

1600

1486

1337

1336

1335

1334

1333

1332

1331

1330

1329

1328

1327

1326

1325

1324

1323

1322

1321

1320

1319

1318

1317

1316

1315

1314

1313

1312

1311

1310

1309

1308

1307

1306

1305

1304

1303

1302

1301

1446

1599

1487

1338

1197

1196

1195

1194

1193

1192

1191

1190

1189

1188

1187

1186

1185

1184

1183

1182

1181

1180

1179

1178

1177

1176

1175

1174

1173

1172

1171

1170

1169

1168

1167

1166

1165

1164

1163

1300

1445

1598

1488

1339

1198

1065

1064

1063

1062

1061

1060

1059

1058

1057

1056

1055

1054

1053

1052

1051

1050

1049

1048

1047

1046

1045

1044

1043

1042

1041

1040

1039

1038

1037

1036

1035

1034

1033

1162

1299

1444

1597

1489

1340

1199

1066

941

940

939

938

937

936

935

934

933

932

931

930

929

928

927

926

925

924

923

922

921

920

919

918

917

916

915

914

913

912

911

1032

1161

1298

1443

1596

1490

1341

1200

1067

942

825

824

823

822

821

820

819

818

817

816

815

814

813

812

811

810

809

808

807

806

805

804

803

802

801

800

799

798

797

910

1031

1160

1297

1442

1595

1491

1342

1201

1068

943

826

717

716

715

714

713

712

711

710

709

708

707

706

705

704

703

702

701

700

699

698

697

696

695

694

693

692

691

796

909

1030

1159

1296

1441

1594

1492

1343

1202

1069

944

827

718

617

616

615

614

613

612

611

610

609

608

607

606

605

604

603

602

601

600

599

598

597

596

595

594

593

690

795

908

1029

1158

1295

1440

1593

1493

1344

1203

1070

945

828

719

618

525

524

523

522

521

520

519

518

517

516

515

514

513

512

511

510

509

508

507

506

505

504

503

592

689

794

907

1028

1157

1294

1439

1592

1494

1345

1204

1071

946

829

720

619

526

441

440

439

438

437

436

435

434

433

432

431

430

429

428

427

426

425

424

423

422

421

502

591

688

793

906

1027

1156

1293

1438

1591

1495

1346

1205

1072

947

830

721

620

527

442

365

364

363

362

361

360

359

358

357

356

355

354

353

352

351

350

349

348

347

420

501

590

687

792

905

1026

1155

1292

1437

1590

1496

1347

1206

1073

948

831

722

621

528

443

366

297

296

295

294

293

292

291

290

289

288

287

286

285

284

283

282

281

346

419

500

589

686

791

904

1025

1154

1291

1436

1589

1497

1348

1207

1074

949

832

723

622

529

444

367

298

237

236

235

234

233

232

231

230

229

228

227

226

225

224

223

280

345

418

499

588

685

790

903

1024

1153

1290

1435

1588

1498

1349

1208

1075

950

833

724

623

530

445

368

299

238

185

184

183

182

181

180

179

178

177

176

175

174

173

222

279

344

417

498

587

684

789

902

1023

1152

1289

1434

1587

1499

1350

1029

1076

951

834

725

624

531

446

369

300

239

186

141

140

139

138

137

136

135

134

133

132

131

172

221

278

343

416

497

586

683

788

901

1022

1151

1288

1433

1586

1500

1351

1210

1077

952

835

726

625

532

447

370

301

240

187

142

105

104

103

102

101

100

99

98

97

130

171

220

277

342

415

496

585

682

787

900

1021

1150

1287

1432

1585

1501

1352

1211

1078

953

836

727

626

533

448

371

302

241

188

143

106

77

76

75

74

73

72

71

96

129

170

219

276

341

414

495

584

681

786

899

1020

1149

1286

1431

1584

1502

1353

1212

1079

954

837

728

627

534

449

372

303

242

189

144

107

78

57

56

55

54

53

70

95

128

169

218

275

340

413

494

583

680

785

898

1019

1148

1285

1430

1583

1503

1354

1213

1080

955

838

729

628

535

450

373

304

243

190

145

108

79

58

45

44

43

52

69

94

127

168

217

274

339

412

493

582

679

784

897

1018

1147

1284

1429

1582

1504

1355

1214

1081

956

839

730

629

536

451

374

305

244

191

146

109

80

59

46

41

42

51

68

93

126

167

216

273

338

411

492

581

678

783

896

1017

1146

1283

1428

1581

1505

1356

1215

1082

957

840

731

630

537

452

375

306

245

192

147

110

81

60

47

48

49

50

67

92

125

166

215

272

337

410

491

580

677

782

895

1016

1145

1282

1427

1580

1506

1357

1216

1083

958

841

732

631

538

453

376

307

246

193

148

111

82

61

62

63

64

65

66

91

124

165

214

271

336

409

490

579

676

781

894

1015

1144

1281

1426

1579

1507

1358

1217

1084

959

842

733

632

539

454

377

308

247

194

149

112

83

84

85

86

87

88

89

90

123

164

213

270

335

408

489

578

675

780

893

1014

1143

1280

1425

1578

1508

1359

1218

1085

960

843

734

633

540

455

378

309

248

195

150

113

114

115

116

117

118

119

120

121

122

163

212

269

334

407

488

577

674

779

892

1013

1142

1279

1424

1577

1509

1360

1219

1086

961

844

735

634

541

456

379

310

249

196

151

152

153

154

155

156

157

158

159

160

161

162

211

268

333

406

487

576

673

778

891

1012

1141

1278

1423

1576

1510

1361

1220

1087

962

845

736

635

542

457

380

311

250

197

198

199

200

201

202

203

204

205

206

207

208

209

210

267

332

405

486

575

672

777

890

1011

1140

1277

1422

1575

1511

1362

1221

1088

963

846

737

636

543

458

381

312

251

252

253

254

255

256

257

258

259

260

261

262

263

264

265

266

331

404

485

574

671

776

889

1010

1139

1276

1421

1574

1512

1363

1222

1089

964

847

738

637

544

459

382

313

314

315

316

317

318

319

320

321

322

323

324

325

326

327

328

329

330

403

484

573

670

775

888

1009

1138

1275

1420

1573

1513

1364

1223

1090

965

848

739

638

545

460

383

384

385

386

387

388

389

390

391

392

393

394

395

396

397

398

399

400

401

402

483

572

669

774

887

1008

1137

1274

1419

1572

1514

1365

1224

1091

966

849

740

639

546

461

462

463

464

465

466

467

468

469

470

471

472

473

474

475

476

477

478

479

480

481

482

571

668

773

886

1007

1136

1273

1418

1571

1515

1366

1225

1092

967

850

741

640

547

548

549

550

551

552

553

554

555

556

557

558

559

560

561

562

563

564

565

566

567

568

569

570

667

772

885

1006

1135

1272

1417

1570

1516

1367

1226

1093

968

851

742

641

642

643

644

645

646

647

648

649

650

651

652

653

654

655

656

657

658

659

660

661

662

663

664

665

666

771

884

1005

1134

1271

1416

1569

1517

1368

1227

1094

969

852

743

744

745

746

747

748

749

750

751

752

753

754

755

756

757

758

759

760

761

762

763

764

765

766

767

768

769

770

883

1004

1133

1270

1415

1568

1518

1369

1228

1095

970

853

854

855

856

857

858

859

860

861

862

863

864

865

866

867

868

869

870

871

872

873

874

875

876

877

878

879

880

881

882

1003

1132

1269

1414

1567

1519

1370

1229

1096

971

972

973

974

975

976

977

978

979

980

981

982

983

984

985

986

987

988

989

990

991

992

993

994

995

996

997

998

999

1000

1001

1002

1131

1268

1413

1566

1520

1371

1230

1097

1098

1099

1100

1101

1102

1103

1104

1105

1106

1107

1108

1109

1110

1111

1112

1113

1114

1115

1116

1117

1118

1119

1120

1121

1122

1123

1124

1125

1126

1127

1128

1129

1130

1267

1412

1565

1521

1372

1231

1232

1233

1234

1235

1236

1237

1238

1239

1240

1241

1242

1243

1244

1245

1246

1247

1248

1249

1250

1251

1252

1253

1254

1255

1256

1257

1258

1259

1260

1261

1262

1263

1264

1265

1266

1411

1564

1522

1373

1374

1375

1376

1377

1378

1379

1380

1381

1382

1383

1384

1385

1386

1387

1388

1389

1390

1391

1392

1393

1394

1395

1396

1397

1398

1399

1400

1401

1402

1403

1404

1405

1406

1407

1408

1409

1410

1563

1523

1524

1525

1526

1527

1528

1529

1530

1531

1532

1533

1534

1535

1536

1537

1538

1539

1540

1541

1542

1543

1544

1545

1546

1547

1548

1549

1550

1551

1552

1553

1554

1555

1556

1557

1558

1559

1560

1561

1562

 

Рис. 1а

 

В этой спирали все 40 простых чисел, которые даёт рассматриваемый трёхчлен Эйлера при x = 0, 1, 2, …, 39, расположились на диагонали квадрата 40х40.

Аналогичный квадратичный трёхчлен, который тоже найден Эйлером: x2 + x + 17. Этот трёхчлен при x, принимающем значения от 0 до 15, даёт только простые числа. На рис. 1б вы видите спираль Улама для этого трёхчлена.

 

272

271

270

269

268

267

266

265

264

263

262

261

260

259

258

257

213

212

211

210

209

208

207

206

205

204

203

202

201

200

199

256

214

161

160

159

158

157

156

155

154

153

152

151

150

149

198

255

215

162

117

116

115

114

113

112

111

110

109

108

107

148

197

254

216

163

118

81

80

79

78

77

76

75

74

73

106

147

196

253

217

164

119

82

53

52

51

50

49

48

47

72

105

146

195

252

218

165

120

83

54

33

32

31

30

29

46

71

104

145

194

251

219

166

121

84

55

34

21

20

19

28

45

70

103

144

193

250

220

167

122

85

56

35

22

17

18

27

44

69

102

143

192

249

221

168

123

86

57

36

23

24

25

26

43

68

101

142

191

248

222

169

124

87

58

37

38

39

40

41

42

67

100

141

190

247

223

170

125

88

59

60

61

62

63

64

65

66

99

140

189

246

224

171

126

89

90

91

92

93

94

95

96

97

98

139

188

245

225

172

127

128

129

130

131

132

133

134

135

136

137

138

187

244

226

173

174

175

176

177

178

179

180

181

182

183

184

185

186

243

227

228

229

230

231

232

233

234

235

236

237

238

239

240

241

242

 

Рис. 1б

 

Все 16 первых простых чисел, которые порождает данный трёхчлен, тоже расположились на диагонали квадрата. В квадрате выделены также остальные простые числа, находящиеся на этой спирали Улама. Интересно отметить, что те же самые 16 простых чисел этот трёхчлен даёт при x, принимающем значения от -1 до -16. Преобразовав рассматриваемый трёхчлен, можно получить такое выражение:

 

(x + 1)2 – (x + 1) + 17 = y2y + 17

 

Новый трёхчлен порождает те же самые простые числа при y, принимающем значения от 1 до 16 (или при y = 0, -1, -2, …, -15). Точно так же можно записать и рассмотренный выше трёхчлен Эйлера:

 

y2 – y + 41

 

Этот трёхчлен порождает те же самые 40 простых чисел при y = 1, 2, 3, …, 40 (или при y = 0, -1, -2, …, -39).

М. Гарднер в своей книге пишет: спираль Улама – забава, но её следует принимать всерьёз.

 

В [5] написано: легко доказать, что не существует многочлена от одной переменной, значения которого при всех целых значениях переменной есть простые числа. Вместе с тем, советский математик Ю. В. Матиясевич доказал, что существует многочлен от нескольких переменных, который принимает все простые значения по одному разу, причём все положительные его значения – простые числа.

 

И ещё одна формула для простых чисел была предложена П. Ферма. Он высказал предположение, что все числа вида 2p + 1, где p = 2k, простые. При k = 0, 1, 2, 3 , 4 получаются такие простые числа: 3, 5, 17, 257, 65537. Однако Эйлер опроверг это предположение, доказав, что при k = 5 число 2p + 1 (p = 25) составное. В самом деле:

 

232 + 1 = 4294967297 = 641 * 6700417

 

В [3] написано, что вопрос о том, при каких значениях k числа указанного вида являются простыми, остаётся и по сей день нерешённым. Вполне возможно, что в настоящее время уже есть ответ на этот вопрос или хотя бы приближение к ответу.

 

 

   

Пьер Ферма (1601 – 1665)

 

Примечание: портрет Пьера Ферма из [5].

 

Кстати, с простыми числами указанного вида связана задача  о том, какие правильные многоугольники можно построить с помощью циркуля и линейки. Гаусс установил, что для всех простых n, имеющих вид:

 

n = 2p + 1 (p = 2k)

 

возможно деление окружности на равные части циркулем и линейкой; при других же простых значениях n такое деление невозможно.

Для случаев n = 3 и n = 5 деление окружности на n равных частей с помощью циркуля и линейки было хорошо известно ещё в древности. А вот построение правильного семнадцатиугольника посредством циркуля и линейки было обнаружено Гауссом впервые. [3]

 

Как уже было отмечено, современные компьютеры по составленным программам, заложенным в пакеты математических программ типа Maple, могут в считанные секунды проверить очень большие числа на простоту. Во времена Эйлера такая проверка даже для шести- и семизначных чисел требовала длительных вычислений. Эйлер однажды заявил, что число 1000009 простое, но потом обнаружил, что оно является произведением двух простых чисел: 293 и 3413. По тем временам это было крупное достижение, если к тому же учесть, что Эйлеру в это время было за 70 и он уже ослеп. Пьера Ферма в одном из писем спросили, простое ли число 100895598169. Он очень быстро ответил, что это число является произведением таких простых чисел: 898423 и 112303. В 1874 г. У. Стенли Джевонс вопрошал в своей книге “Основы науки”: “Может ли читатель сказать, произведение каких двух чисел равно 8616460799? Думаю, что вряд ли кто-нибудь, кроме меня самого, сумеет дать ответ на этот вопрос, ибо это два больших простых числа”. Конечно, Джевонс не мог знать, что современный компьютер найдёт оба эти числа быстрее, чем он мог бы их перемножить. [2]

 

Оказывается, натуральные числа раскладываются не только на произведение простых чисел, но и на сумму простых чисел. Это знаменитая проблема Х. Гольдбаха. Гольдбах высказал следующее предположение: а) всякое нечётное число, большее шести, есть сумма трёх простых чисел; б) всякое чётное число есть сумма двух простых чисел.

Например, 25 = 3 + 5 + 17, 26 = 7 + 19, 40 = 17 + 23.

В 1937 г. академик И. М. Виноградов с помощью разработанного им метода оценок тригонометрических сумм доказал, что каждое достаточно большое нечётное число действительно является суммой трёх простых чисел. [6]

Подробнее о других проблемах, связанных с простыми числами, смотрите в статье “Простые числа” в Википедии (ссылка в конце статьи). Как я поняла из этой статьи, проблема Гольдбаха не решена до сих пор.

 

Примечание: если число 1 не считать простым числом, то вторую часть гипотезы Гольдбаха следует сформулировать так: всякое чётное число большее 2 есть сумма двух простых чисел. Однако в [6], откуда я взяла приведённую формулировку этой гипотезы, написано так, как представлено выше. У меня возникает подозрение, что во времена Гольдбаха число 1 считалось простым числом. Тогда всё правильно, число 2 тоже представимо в виде суммы двух простых чисел: 1 + 1. В таком случае первая часть гипотезы автоматически следует из второй части, потому что любое нечётное число есть сумма чётного числа и единицы. Но тогда в первой части гипотезы непонятно ограничение “большее шести”.

В знаменитом магическом квадрате 3-го порядка из простых чисел, построенном Дьюдени, присутствует число 1. Есть это число и в известном магическом квадрате 12-го порядка из простых чисел Дж. Манси, построенном в 1913 г.

 

 

Р Е Ш Е Т О   Э Р А Т О С Ф Е Н А

 

Как же искать простые числа в ряду последовательных натуральных чисел? Древнейший алгоритм такого поиска был предложен 2000 лет назад астрономом и географом из Александрии Эратосфеном. Этот алгоритм получил название “решето Эратосфена”.

Опишу подробно алгоритм Эратосфена. Пусть нам надо найти все простые числа в диапазоне от 1 до N. Выпишем подряд все числа от 2 до N. Зачеркнём в этом списке каждое второе число из следующих за числом 2. Таким образом мы отсеем все числа кратные числу 2. Число 2 является первым простым числом. Следующее не зачёркнутое число в списке после числа 2 – число 3. Это второе простое число. Повторим процедуру отсеивания, только теперь будем зачёркивать каждое третье число из следующих за числом 3. Так отсеем все числа кратные 3. Процедуру отсеивания следует повторять до тех пор, пока не доберёмся до простого числа, которое больше квадратного корня из N. Все числа, оставшиеся не зачёркнутыми в списке, будут простыми. Приведу иллюстрацию описанного метода для N = 50. Сначала покажу, как будет выглядеть список чисел после отсеивания чисел кратных 2:

 

2,  3,  /4/,  5,  /6/,  7,  /8/,  9,  /10/,  11,  /12/,  13,  /14/,  15,  /16/,  17,  /18/,  19,  /20/,  21,  /22/,  23,  /24/,  25,  /26/,  27,  /28/,  29,  /30/

31,  /32/,  33,  /34/,  35,  /36/,  37,  /38/,  39,  /40/,  41,  /42/,  43,  /44/,  45,  /46/,  47,  /48/,  49,  /50/

 

Примечание: зачёркнутые числа заключены в две наклонные черты / /.

 

Теперь покажу, как выглядит список после вычёркивания всех чисел кратных 3:

 

2,  3,  /4/,  5,  /6/,  7,  /8/,  /9/,  /10/,  11,  /12/,  13,  /14/,  /15/,  /16/,  17,  /18/,  19,  /20/,  /21/,  /22/,  23,  /24/,  25,  /26/,  /27/,  /28/,  29,  /30/

31,  /32/,  /33/,  /34/,  35,  /36/,  37,  /38/,  /39/,  /40/,  41,  /42/,  43,  /44/,  /45/,  /46/,  47,  /48/,  49,  /50/

 

Осталось два этапа: вычеркнуть все числа кратные 5 и кратные 7. Окончательно получим такой список простых чисел (простые числа выделены красным цветом):

 

23,  /4/,  5,  /6/,  7,  /8/,  /9/,  /10/,  11,  /12/,  13,  /14/,  /15/,  /16/,  17,  /18/,  19,  /20/,  /21/,  /22/,  23,  /24/,  /25/,  /26/,  /27/,  /28/,  29,  /30/

31,  /32/,  /33/,  /34/,  /35/,  /36/,  37,  /38/,  /39/,  /40/,  41,  /42/,  43,  /44/,  /45/,  /46/,  47,  /48/,  /49/,  /50/

 

В этом примере процедура отсеивания (зачёркивания) завершилась на простом числе 7, то есть последний раз мы зачёркивали в этом списке каждое седьмое число, следующее за числом 7. Числа кратные 11 мы уже не будем зачёркивать (отсеивать), так как это число больше квадратного корня из 50.

 

Покажу ещё один оригинальный приём реализации решета Эратосфена из [2] (стр. 411 – 412). Здесь находятся все простые числа в интервале от 1 до 100. Все числа от 1 до 100 помещаются в прямоугольную таблицу (рис. 2).

 

 

Рис. 2

 

Процедура отсеивания выполняется следующим образом. Вычеркнем все числа кратные 2, за исключением самой двойки, проведя вертикальные черты во втором, четвёртом и шестом столбцах. Вычеркнем все числа кратные 3 (сама тройка остаётся), проведя вертикальную черту в третьем столбце. Следующее за 3 не вычеркнутое число равно 5. Чтобы вычеркнуть числа кратные 5, проведём диагонали, идущие вниз и влево (число 5 остаётся). Оставшиеся в таблице числа кратные 7 вычеркнем, проведя диагонали с наклоном вправо и вниз. Наша работа по составлению списка простых чисел, не превосходящих числа 100, на этом заканчивается, поскольку следующее простое число 11 больше квадратного корня из 100. Если бы таблица была больше, то нам пришлось бы исключать числа кратные 11, проводя диагонали с более крутым наклоном. Все не зачёркнутые числа в таблице на рис. 2, кроме числа 1, являются простыми (они выделены красным цветом).

 

Во времена Эратосфена писали на восковых дощечках, а вместо того, чтобы числа зачёркивать, дощечку в нужном месте прокалывали. Отсюда и произошло название способа – “решето Эратосфена”: составные числа как бы “просеивались” в проколотые дырки, а простые числа оставались в “решете”.

 

Понятно, что алгоритм Эратосфена нетрудно реализовать. Существует множество программ, составленных разными авторами. Есть программа, например, в [4] (стр. 305). Можно посмотреть и реализацию алгоритма, выполненную в Википедии:

 

http://ru.wikipedia.org/wiki/%D0%A0%D0%B5%D1%88%D0%B5%D1%82%D0%BE_%D0%AD%D1%80%D0%B0%D1%82%D0%BE%D1%81%D1%84%D0%B5%D0%BD%D0%B0

 

А лучше всего составить свою программу.

 

 

Р Е Ш Е Т О   С У Н Д А Р А М А

 

Ещё одно интересное “решето” для нахождения простых чисел было предложено в 1934 году индийским математиком С. П. Сундарамом. Он придумал очень оригинальную таблицу, состоящую из бесконечного количества бесконечных арифметических прогрессий, причём каждый член первой прогрессии начинает новую прогрессию (с новой строки таблицы). Разностями прогрессий являются все нечётные числа, начиная с 3. На рис. 3 вы видите начало таблицы Сундарама.

 

4

7

10

13

16

19

22

25

28

31

34

37

7

12

17

22

27

32

37

42

47

52

57

62

10

17

24

31

38

45

52

59

66

73

80

87

13

22

31

40

49

58

67

76

85

94

103

112

16

27

38

49

60

71

82

93

104

115

126

137

19

32

45

58

71

84

97

110

123

136

149

162

22

37

52

67

82

97

112

127

142

157

172

187

25

42

59

76

93

110

127

144

161

178

195

212

28

47

66

85

104

123

142

161

180

199

218

237

31

52

73

94

115

136

157

178

199

220

241

262

34

57

80

103

126

149

172

195

218

241

264

287

 

Рис. 3

 

Таблица бесконечно продолжается вправо и вниз. Разность арифметической прогрессии, записанной в первой строке таблицы, равна 3, разность арифметической прогрессии, записанной во второй строке таблицы, равна 5 и т. д. (все нечётные числа подряд являются разностями прогрессий).

Как же находить простые числа с помощью таблицы Сундарама? Оказывается, эта таблица обладает таким свойством: если некоторое число N содержится в таблице Сундарама, то число 2*N + 1 будет обязательно составным, а если число N не содержится в этой таблице, то число 2*N + 1 будет простым. Например, число 4 содержится в таблице, следовательно, число 2*4 + 1 = 9 составное; числа 5 нет в таблице, следовательно, число 2*5 + 1 = 11 простое. Доказательство этого свойства таблицы Сундарама вы можете найти в [1] (стр. 563 – 564).

 

Я реализовала метод Сундарама. Вот текст программы, написанный на языке QBASIC:

 

Программа для решета Сундарама

 

5 PRINT "VVEDITE M"

7 INPUT M

8 IF INT(M / 2) <> M / 2 THEN 5

9 IF M < 4 THEN 5

10 PRINT "VVEDITE L"

11 INPUT L

12 FOR I = M + 1 TO L STEP 2

15 B = I: A = (B - 1) / 2

17 C = A - 1

20 FOR N = 1 TO C

25 K = (A - N) / (1 + 2 * N)

30 IF INT(K) = K THEN 40

35 NEXT N

36 W = W + 1: PRINT "#"; W

37 PRINT B

40 NEXT I

45 PRINT

50 END

 

 

Программа работает очень просто. Надо ввести в программу чётное натуральное число M ≥ 4 и любое натуральное число L > M. Программа выдаст все простые числа в диапазоне от M+1 до L. Недостаток программы: при M = 4 теряются два простых числа: 2 и 3. Но этот недостаток очень легко устранить, если вставить в программу блок простой печати указанных простых чисел в случае, когда M = 4. По этой программе я получила следующий ряд простых чисел в интервале от 5 до 1000 (M = 4, L = 1000):

 

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

 

Замечу, что при выполнении программы был открыт файл для вывода простых чисел. В приведённом варианте программы простые числа выводятся только на экран монитора. При этом перед каждым простым числом выводится его порядковый номер.

 

А это результат, выданный программой при M = 1000, L = 2000:

 

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  1697  1699  1709  1721  1723  1733  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

 

На форуме dxdy.ru по моей просьбе приведённая программа переписана на двух других языках программирования: Pascal и Turbo C++ 3.0. Вы можете посмотреть эти программы по следующей ссылке:

http://dxdy.ru/post218607.html?sid=6723a4a0d1a58ddd42ca1a8eb19a8f9c#p218607

 

В моей реализации решета Сундарама использовано следующее утверждение:

 

Т Е О Р Е М А   2

 

Любое число A, находящееся в таблице Сундарама, может быть представлено в виде: A = (1 + 2 * N) * K + N,

где N – номер строки таблицы, в которой находится данное число, K – порядковый номер числа в этой строке.

 

 

Теорема доказывается просто. Оставляю доказательство читателям.

 

Другую программу для решета Сундарама вы можете найти в Википедии в статье “Решето Сундарама”:

 

http://ru.wikipedia.org/wiki/%D0%A0%D0%B5%D1%88%D0%B5%D1%82%D0%BE_%D0%A1%D1%83%D0%BD%D0%B4%D0%B0%D1%80%D0%B0%D0%BC%D0%B0

 

Отмечу, что в программе, приведённой в указанной статье Википедии, простые числа находятся только с начала ряда натуральных чисел до некоторого n. В этом неудобство программы в тех случаях, когда простые числа надо найти в некотором интервале, находящемся не в начале натурального ряда. Кроме того, моя реализация принципиально отличается от реализации, приведённой в Википедии. В моей программе меньше циклов и поэтому выполняется она быстрее.

 

Однако решето Сундарама в любом случае не работает для очень больших чисел за реальное время. Так, например, я смогла выполнить свою программу для интервала [107 + 1, 107 + 100) довольно быстро, а при M = 108, L = 108 + 100 программа надолго “задумалась”; я не стала ждать, когда она что-нибудь выдаст, и прервала её.

 

Приведу интересную задачу о простых числах, состоящих из единиц. Генри Э. Дьюдени ещё в 1907 году отметил, что  11 – единственное из известных в то время простых чисел, которое состоит из одних единиц. Понятно, что число, в записи которого участвует любая другая цифра, составное, например: 3333, 55555. Дьюдени доказал, что все числа, состоящие из 3, 4, 5, … , 18 единиц, составные.

Следует заметить, что справедлива следующая теорема:

 

Т Е О Р Е М А   3

 

Если число N составное, то число, составленное из N единиц тоже составное.

 

 

Теорема доказывается очень просто.

Дьюдени заинтересовался такими “единичными” простыми числами. Один из его читателей доказал, что число, состоящее из 19 единиц, простое. Позднее было установлено, что число, записанное с помощью 23 единиц, также простое. В то время, когда я писала книгу, было известно, что числа, состоящие из 29, 31, 37, 41, 43, 53, 61 и 73 единиц, составные. Первым кандидатом на простое было число, составленное из 47 единиц. Я попробовала решить эту задачу, то есть установить, является ли число, состоящее из 47 единиц, простым. И сделать это пыталась как раз с помощью приведённой в теореме 2 формулы. Обозначим число, состоящее из 47 единиц, В. Чтобы ответить на вопрос, является число В простым или составным, надо установить, находится ли соответствующее ему число А в таблице Сундарама. Число А находится из уравнения:

 

2 * A + 1 = B

 

Получаем, что число А = 55…5 (в записи числа А имеется 46 пятёрок).

Согласно теореме 2, если число А находится в таблице Сундарама, то оно должно быть представимо в виде:

 

A = (1 + 2 * N) * K + N,

 

где K и N – натуральные числа. Следовательно, задача свелась к решению приведённого уравнения в натуральных числах. Удобнее представить это уравнение в таком виде:

 

[1]                                 K = (AN)/(1 + 2 * N)

 

Эта формула и положена в основу моей реализации решета Сундарама. Если данное уравнение не имеет решения в натуральных числах, то числа А нет в таблице Сундарама, а это означает, что соответствующее число В = 2 * А + 1 простое.

Однако для числа А, состоящего из 46 пятёрок, мне не удалось решить это уравнение (язык QBASIC не работает с такими большими числами). Поэтому эта задача тогда так и осталась у меня нерешённой.

Сейчас существует пакет математических программ Maple, который позволяет решать аналогичные задачи за одну секунду. На форуме, где я привела эту задачу, её решили сразу с помощью Maple. Оказалось, что число, составленное из 47 единиц, составное. Однако мне так и не ответили на вопрос, чему равны K и N, то есть в какой строке и с каким порядковым номером в этой строке находится в таблице Сундарама число А, состоящее из 46 пятёрок. А коль скоро число В, состоящее из 47 единиц, составное, число А, состоящее из 46 пятёрок, обязательно содержится в таблице Сундарама.

Приведу пример для небольшого числа А. Пусть А = 5555. В этом случае уравнение [1] имеет такое решение: N = 20, K = 135. Это значит, что в 20-ой строке таблицы Сундарама 135-ый член равен 5555, следовательно, число В = 2 * 5555 + 1 = 11111 составное.

 

Примечание: отмечу, что уравнение [1] в случае, когда число A содержится в таблице Сундарама, имеет не единственное решение. Рассмотрим пример для A = 22. Это число находится в таблице Сундарама в четырёх строках: первой, второй, четвёртой и седьмой.. Соответственно уравнение [1] имеет четыре решения:

 

1. N = 1, K = 7

2. N = 2, K = 4

3. N = 4, K = 2

4. N = 7, K = 1.

 

Только при A = 4 решение уравнения [1] будет единственным: N = 1, K = 1.

Для решения вопроса, является число B = 2*A + 1 простым или составным, достаточно найти одно решение уравнения [1] в натуральных числах.

 

С помощью приведённой выше программы для решета Сундарама можно проверить не очень большое число, является ли оно простым. Приведу два примера.

 

Пример 1. Требуется проверить число 105 + 1. Введём в программу M = 105, L = 105 + 1. Программы выполнит проверку только одного числа M + 1 = 105 + 1. Результат – данное число составное.

 

Пример 2. Требуется проверить число 106 + 121. Введём в программу M = 106 + 120, L = 106 + 121. Программы выполнит проверку числа M + 1 = 106 + 121. Результат выполнения программы – это число простое (программа выведет его на экран монитора).

 

Ещё один алгоритм нахождения простых чисел не связан ни с решетом Эратосфена, ни с решетом Сундарама. Здесь всё выполняется, что называется, “в лоб”: для каждого числа N проверяется, нет ли у него делителей в интервале от 2 до [√ N]. Реализацию этого алгоритма тоже можно найти в [4] (стр. 306). Впрочем, алгоритм очень просто реализовать.

 

 

Р Е Ш Е Т О   А Т К И Н А

 

Решето Аткина – это современный оптимизированный вариант решета Эратосфена. Прежде всего, дам ссылку на статью об этом решете в Википедии:

 

http://ru.wikipedia.org/wiki/%D0%A0%D0%B5%D1%88%D0%B5%D1%82%D0%BE_%D0%AD%D1%80%D0%B0%D1%82%D0%BE%D1%81%D1%84%D0%B5%D0%BD%D0%B0

 

Я не разбиралась с этим решетом. Предоставляю данный метод читателям для самостоятельного изучения. В помощь даю ссылку на форум “Портал Естественных Наук”, где в теме “Алгоритм «решета Эратосфена»” подробно рассматривается вопрос о решете Аткина, приведён текст программы, как я поняла, полученный из текста в Википедии незначительными изменениями. Вот ссылка:

 

http://e-science.ru/forum/index.php?s=80eab7d3816a082e5ee44635ec254896&showtopic=12506&st=80

 

 

Ч И С Л А   М Е Р С Е Н Н А

 

Числа вида 2p – 1, где p – простое число, называются числами Мерсенна, впервые заметившего, что среди таких чисел много простых. В течение почти 200 лет математики считали, что число Мерсенна 267 – 1 простое. Эрик Темриль Белл в своей книге “Математика – царица и служанка науки” рассказывает о заседании американского математического общества, состоявшемся в октябре 1903 г. в Нью-Йорке, на котором выступил с сообщением профессор Коул. “Коул, человек немногословный, подошёл к доске и, не говоря ни слова, начал возводить 2 в степень 67. Затем он вычел из полученного числа 1 и, по-прежнему не говоря ни слова, перешёл на чистую часть доски, где столбиком перемножил два числа: 193707721 и 761838257287. Оба результата совпали… Впервые в истории американского математического общества его члены бурными аплодисментами приветствовали докладчика. Коул, так и не проронив ни слова, сел на место. Никто не задал ему ни одного вопроса. Через несколько лет Белл спросил у Коула, сколько времени тот потратил, чтобы разложить число на множители. ”Все воскресенья в течение трёх лет”, - ответил Коул. [2]

 

Далее приведены девять первых чисел Мерсенна, среди которых выделены красным цветом простые числа:

 

3,   7,   31127,   2047,  8191131071524287,  8388607

Как видите, среди первых девяти чисел Мерсенна только два составные. В то время, когда Гарднер писал свою книгу “Математические досуги”, было известно такое максимальное простое число Мерсенна: 211213 – 1. Запись этого числа содержит около 3376 цифр. Это число обнаружил в 1963 г. с помощью ЭВМ Дональд Б. Джиллис. Это же число являлось и самым большим из известных простых чисел. [2]

В [5] уже приводится гораздо большее простое число Мерсенна:  2132049 – 1. И опять же это число было самым большим из известных простых чисел.

В настоящее время составлены специальные программы для поиска чисел Мерсенна. Смотрите, например, тему “Взаимно простые числа” форума “Портал Естественных Наук”:

 

http://e-science.ru/forum/index.php?showtopic=9777

 

В статье “Простые числа” Википедии (ссылку см. в конце статьи) сообщается, что самым большим простым числом по состоянию на сентябрь 2008 г. является число Мерсенна  243112609 – 1. Оно было найдено 23 августа 2008 г. на математическом факультете университета UCLA в рамках проекта по распределённому поиску чисел Мерсенна GIMPS. В десятичной записи этого числа содержится около 13 миллионов цифр. Это 46-ое число Мерсенна. Насколько  понимаю, 47-ое число Мерсенна ещё не найдено.

Поскольку для чисел Мерсенна существует тест проверки на простоту, уже несколько лет именно эти числа держат рекорд самого большого простого числа.

 

 

В З А И М Н О   П Р О С Т Ы Е   Ч И С Л А

 

Два числа n и m называются взаимно простыми, если они не имеют общих делителей, кроме 1. Обычно это записывают так: (n, m) = 1.

Так, например, числа 10 и 33 взаимно просты. Чтобы определить, являются ли два числа взаимно простыми, надо разложить их на простые множители.

Если p – простое число и a не делится на p, то n = (ap-1 – 1) всегда делится на p. Эта теорема носит название “малой теоремы Ферма”; она имеет очень большое значение для теории сравнений.

Эйлер ввёл функцию φ(m), которая называется функцией Эйлера. Эта функция определяет количество натуральных чисел меньших числа m и взаимно простых с ним. Так, φ(6) = 2, φ(10) = 4. Если m простое число, то все меньшие числа взаимно просты с m и φ(m) = m – 1. Например, φ(11) = 10.

Эйлер обобщил малую теорему Ферма и доказал, что если a и m взаимно простые числа, то (aφ(m) – 1) делится на m. Это утверждение называется теоремой Эйлера о сравнениях. [6]

 

 

М А Г И Ч Е С К И Е   К В А Д Р А Т Ы   И З   П Р О С Т Ы Х   Ч И С Е Л

 

Если вы ещё не знаете, что такое магический квадрат, скачайте и прочтите книгу “Волшебный мир магических квадратов”:

 

http://narod.ru/disk/5834353000/Magic_squares.pdf.html

 

Вопрос составления нетрадиционных магических квадратов из простых чисел давно занимает математиков. Первый такой квадрат построил Дьюдени, это был квадрат 3-го порядка. Его магическая константа равна 111. Дьюдени доказал, что это минимальная константа для магических квадратов, составленных из простых чисел. Вы видите квадрат Дьюдени на рис. 4.

 

67

1

43

13

37

61

31

73

7

 

Рис. 4

 

Примечание: в квадрате, правда, присутствует число 1, которое в современной теории чисел не считается простым числом.

 

В квадрате Дьюдени числа не последовательные. Понятно, что единственное чётное простое число 2 нельзя вписать ни в один магический квадрат, так как сумма чисел в той строке или в том столбце, на пересечении которых находится число 2, отличалась бы по чётности от суммы чисел во всех остальных строках и столбцах, и квадрат не был бы магическим. Поэтому магический квадрат из последовательных простых чисел был составлен без участия простого числа 2  (и опять же участвует число 1, которое не относится к простым числам). Этот магический квадрат составил Дж. Н. Манси в 1913 г. Это квадрат 12-го порядка, в его ячейках расположены 143 первых нечётных простых числа (число 1 не считаем). Манси доказал, что наименьший магический квадрат из последовательных нечётных простых чисел должен иметь порядок 12. Магический квадрат Манси изображён на рис. 5.

 

1

823

821

809

811

797

19

29

313

31

23

37

89

83

211

79

641

631

619

709

617

53

43

739

97

227

103

107

193

557

719

727

607

139

757

281

223

653

499

197

109

113

563

479

173

761

587

157

367

379

521

383

241

467

257

263

269

167

601

599

349

359

353

647

389

331

317

311

409

307

293

449

503

523

233

337

547

397

421

17

401

271

431

433

229

491

373

487

461

251

443

463

137

439

457

283

509

199

73

541

347

191

181

569

577

571

163

593

661

101

643

239

691

701

127

131

179

613

277

151

659

673

677

683

71

67

61

47

59

743

733

41

827

3

7

5

13

11

787

769

773

419

149

751

 

Рис. 5

 

Магическая константа этого квадрата равна 4514. [2]

 

В Википедии в статье “Магический квадрат” приведён ещё один нетрадиционный квадрат, заполненный простыми числами, показываю его на рис. 6.

 

17

89

71

113

59

5

47

29

101

 

Рис. 6

 

В этом квадрате нет числа 1, все числа простые. Магическая константа квадрата равна 177.

 

А теперь представьте, что вам надо построить другие нетрадиционные магические квадраты, скажем, тоже 3-го порядка, заполненные только простыми числами. Как вы будете строить такие магические квадраты? Ну, для порядка 3 можно обойтись без всякого особого алгоритма, а просто ввести некоторый массив простых чисел и перебирать все числа из этого массива на предмет их расположения в магическом квадрате 3х3. По такой программе вам удастся довольно быстро строить магические квадраты. Только надо учесть, что в нетрадиционном магическом квадрате 3-го порядка, составленном из простых чисел, не может быть записано не только число 2, но и число 3 (доказано в [7]). Поэтому массив простых чисел надо брать, начиная с числа 5. На рис. 7 вы видите три магических квадрата, построенные по такой программе.

 

29

131

107

 

37

79

103

 

59

53

101

167

89

11

139

73

7

113

71

29

71

47

149

 

43

67

109

 

41

89

83

 

Рис. 7

 

Для порядка 3 программа работает быстро и эффективно. Вы можете построить сколько угодно подобных магических квадратов.

Разумеется, это решение не является самым лучшим. В [7] приводится теория построения нетрадиционных магических квадратов из простых чисел не только 3-го порядка. Кстати, приводится нетрадиционный магический квадрат 9-го порядка (стр. 206), составленный из простых чисел. Этот квадрат состоит из девяти нетрадиционных магических квадратов 3-го порядка. В книге написано, что этот квадрат 9-го порядка является “наименьшим из всех магических квадратов такого рода”. Что автор имел в виду под “наименьшим”? Возможно, то, что этот квадрат имеет минимальную магическую константу. Воспроизведу этот квадрат (рис. 8):

 

2531

17

1409

1097

71