Сравнения с остатък

[MilenaGeorgieva]

Привет, моля да съдействате с решението на следната задача:

Да се намери остатъкът на числото 22!-22 по модул 46.

[pal702004]

Бих посъветвал да се намерят остатъците по модули 2 и 23. Първото е тривиално, второто също - теорема на Уилсън.
(Остатъка е $0$ - дели се точно.)

[MilenaGeorgieva]

Благодаря за отговора, но може подробно да го опишете?

[pal702004]

Теорема на Уилсън

$23$ е просто число, следователно $22! \equiv -1 \pmod {23}$

$22!-22 \equiv -1-22 =-23 \equiv 0 \pmod{23}$

Тоест, $22!-22$ се дели на $23$. Дели се също така и на $2$, а значи се дели на $2\cdot 23$

[MilenaGeorgieva]

Моля за помощ и в тези задачи:

1. Да се намерят всички прости числа p,q и r, такива че p^q+1=r

2. Да се намерят всички естествени числа n, за които числото (n^2-2n-2)^2-35 е точен квадрат.

3. Да се докаже че ако сравнението x^5==-1(mod p) има решение по модул простото число p, то p==1(mod10)

4. Да се намерят всички естествени числа n, за които 13|2^n+3^n

[pal702004]

Зависи какво разбираме под "малко" помощ...

1. Обикновено простите числа са нечетни. Може ли и трите да са нечетни? (Въобще, може ли $q$ да е нечетно)

2, С малко изключения $(X-1)^2<X^2-35<X^2$ за естествено число $X$ и не може да бъде точен квадрат.

3. В такава формулировка твърдението не е вярно. Трябва да се добави условие $x \not \equiv -1 \pmod p$

Защото иначе $2^5 \equiv -1 \mod 3$, обаче $3 \not \equiv 1 \pmod {10}$

$6^5 \equiv -1 \pmod 7$, но $7 \not \equiv 1 \pmod{10}$ и т.н.
Като уточнихме формулировката, може да се реши задачата с помощта на квадратичния закон за взаимност, но може просто с помощта на малката теорема на Ферма.

$x^5 \equiv -1 \pmod p \Longrightarrow x^{10} \equiv 1 \pmod p$

Нека за някое $x$, числото $k$ да е най-малкото ествествено, такова че $x^k \equiv 1 \pmod p$

От МТФ знаем, че $k$ трябва да е делител на $p-1$
Сега виждаме, че $k$ трябва да е делител на $10$, при това $k \ne 5$

При $k=1,k=2$ стигаме до решението $x \equiv -1 \pmod p$
(всъщност и $k=1$ трябва да го изключим,защото тогава $x^5 \equiv +1 \pmod p$)

При $k=10$ стигаме до извода, че $10$ е делител на $p-1$, тоест, $p=10n+1$

4. Просто проверете $n \in \{1,2,3,4\}$