Делимост

[Гост]

Да се намерят всички естествени числа n, такива че n дели [tex]3^{n }[/tex]+[tex]1^{ }[/tex]

[pal702004]

Аха,
$n=1,n=2,n=2\cdot 5^k \;\; \forall k \in \mathbb{N}$

Без доказателство за пълнота.

Откъде е задачата?

[Гост]

"Задачи за подготовка за математически олимпиади" на Георги Паскалев и Пламен Пенчев.

[pal702004]

Идея си нямам какво очакват авторите като решение. Те са безброй много и не се поддават на формализация. Знaейки, че при $n=10$ условието е изпълнено, да потърсим решение във вид $n=10p$ където $p$ е просто, различно от 5. Делимост на 10 е осигурена за всяко нечетно $p$, така че остава делимост на $p$

$3^{10p}+1=3^{10(p-1)}\cdot 3^{10}+1 \equiv 0 \pmod p$. Тоест, всеки прост делител на $3^{10}+1$ върши работа. Такъв е $1181$, тоест, $n=11810$ също е решение, и следователно, според LTE решение и $n=10\cdot 1181^k$.

Сега можем да пробваме $n=50p$ и пак ще се получи - $p=394201$ или $p=61070817601$

Да проверим $n=50*394201=19710050$

Проверка

Ами да. Как очакват авторите да се опишат ВСИЧКИ решения - идея си нямам. Мисля, че те също не са наясно каква задача са измислили.

[Гост]

По-принцип наскоро видях на едно място същата задача, но с изискването n да е нечетно, което, оказва се, облекчава решението. Въпреки това трябва да отбележа, че в "Задачи за подготовка за математически олимпиади" задачата не съдържа това допълнително условие и в случая, когато n е четно, решението дадено там напомня това на pal702004 - дава се нещо като алгоритъм за генериране на безбройно много прости числа, делящи n и се заключава, че n не се дели на други прости числа т.е. на практика решенията не се поддават на формализация, както вече спомена pal702004.