57 lines
1.9 KiB
Markdown
57 lines
1.9 KiB
Markdown
---
|
||
id: 5900f5241000cf542c510036
|
||
title: 'Завдання 437: Прості корені Фібоначчі'
|
||
challengeType: 5
|
||
forumTopicId: 302108
|
||
dashedName: problem-437-fibonacci-primitive-roots
|
||
---
|
||
|
||
# --description--
|
||
|
||
Коли ми підраховуємо $8^n$ модуль 11 для $n = 0$ до 9, ми отримуємо: 1, 8, 9, 6, 4, 10, 3, 2, 5, 7.
|
||
|
||
Очевидно, виникають усі можливі значення від 1 до 10. Тож 8 - це простий корінь з 11.
|
||
|
||
Проте це не все:
|
||
|
||
Якщо розглянути детальніше, то:
|
||
|
||
$$\begin{align} & 1 + 8 = 9 \\\\
|
||
& 8 + 9 = 17 ≡ 6\bmod 11 \\\\ & 9 + 6 = 15 ≡ 4\bmod 11 \\\\
|
||
& 6 + 4 = 10 \\\\ & 4 + 10 = 14 ≡ 3\bmod 11 \\\\
|
||
& 10 + 3 = 13 ≡ 2\bmod 11 \\\\ & 3 + 2 = 5 \\\\
|
||
& 2 + 5 = 7 \\\\ & 5 + 7 = 12 ≡ 1\bmod 11. \end{align}$$
|
||
|
||
Тож степінь з 8 модуля 11 є циклічним в 10 періоді, а $8^n + 8^{n + 1} ≡ 8^{n + 2} (\text{mod } 11)$. Число 8 називають простим коренем Фібоначчі для 11.
|
||
|
||
Не кожне просте число має простий корінь Фібоначчі. Існує на 323 простих числа менших за 10000 з одним або більше простим коренем Фібоначчі і сумою цих простих чисел є 1480491.
|
||
|
||
Знайдіть суму простих чисел, менших за $100\\,000\\,000$ з хоча б одним простим коренем Фібоначчі.
|
||
|
||
# --hints--
|
||
|
||
`fibonacciPrimitiveRoots()` має видати `74204709657207`.
|
||
|
||
```js
|
||
assert.strictEqual(fibonacciPrimitiveRoots(), 74204709657207);
|
||
```
|
||
|
||
# --seed--
|
||
|
||
## --seed-contents--
|
||
|
||
```js
|
||
function fibonacciPrimitiveRoots() {
|
||
|
||
return true;
|
||
}
|
||
|
||
fibonacciPrimitiveRoots();
|
||
```
|
||
|
||
# --solutions--
|
||
|
||
```js
|
||
// solution required
|
||
```
|