Теореми Ферма, Ойлер и Уилсън - задачи

[chef_georg]

Имам огромни затруднения с тези задачи. Моля за решенията им

Задача 1. Намерете последните две цифри на числото [tex]3^{а}[/tex] (записано в десетична
бройна система), където числото a = 2030015313

Задача 2. Докажете, че числата 21n + 4 и 14n + 3 са взаимно прости за всяко
естествено число n.

Задача 3. Докажете, че ако p и q са прости числа, по-големи от 3, то [tex]p^{2}[/tex] - [tex]q^{2}[/tex]
се дели на 24.

Задача 4. Да се намерят всички двойки (p; n), където p е просто число, а n е
естествено число, за които
(а) [tex]p^{2}[/tex] дели [tex]11^{p^{2}}[/tex]- 1; (б) [tex]p^{n}[/tex] дели [tex]10^{p^{n}}[/tex]- 1.

[pandora]

https://store.fmi.uni-sofia.bg/fmi/alge ... _AA_MS.pdf
мога да споделя това ръководство, тъй като нз доколко са ми верни и аз питах за тези задачи, но също нямам отговор

[chef_georg]

Благодаря! Това ръководство го прочетох 10 пъти и по никакъв начин не ми помогна

[silvipl]

Здравей, тук има 3 от задачите
viewtopic.php?f=27&t=23319&fbclid=IwAR0nIn_glpfhCYktjPJ4tkXvELk1cBvBx0KhfAHOyBFvY9hOQCYSpsVdbIc

[Добромир Глухаров]

Задача 1 Теорема на Ойлер: $3^{k.\varphi(100)}\equiv1(mod100)$

$3^{40k}\equiv1(mod100)\Rightarrow3^{2030015313}\equiv3^{40.25.2030015+313}\equiv3^{313}\equiv3^{7.40+33}\equiv3^{33}(mod100)$

$3^{33}\equiv3^{4.8+1}\equiv3.81^8\equiv3.(-19)^8\equiv3.361^4\equiv3.61^4\equiv3.13845841\equiv3.41\equiv23(mod100)$

$\Rightarrow3^{2030015313}$ завършва на 23.

Задача 2 Алгоритъм на Евклид: $a>b\Rightarrow(a,b)=(b,a-b)$ ((a,b) - НОД на a и b).

$(21n+4,14n+3)=(14n+3,7n+1)=(7n+1,7n+2)=(7n+2,7n+1)=(7n+1,1)=1$

Следователно $21n+4$ и $14n+3$ са взаимно прости.

Задача 3 $p,q\in\mathbb{P},p>q>3$

$p^2-q^2=(q+2k)-q^2=4qk+4k^2=4k(q+k),k\in\mathbb{N}$

I. q е нечетно и или к е четно, или е нечетно:

$\to k$ - четно $\Rightarrow8|(p^2-q^2)$
$\to k$ - нечетно $\Rightarrow2|(q+k)\Rightarrow8|(p^2-q^2)$

II. $q\not\equiv0(mod3)$

Ако $3|k\Rightarrow3|(p^2-q^2)\Rightarrow24|(p^2-q^2)$

Ако $q\equiv2(mod3)\Rightarrow k\not\equiv2(mod3)$, в противен случай $3|(q+2k)\Rightarrow3|p$ - противоречие с условието. Следователно $k+q\equiv1+2(mod3)\Rightarrow3|(k+q)\Rightarrow24|(p^2-q^2)$

Ако $q\equiv1(mod3)\Rightarrow k\not\equiv1(mod3)$, в противен случай $3|(q+2k)\Rightarrow3|p$ - противоречие с условието. Следователно $k+q\equiv2+1(mod3)\Rightarrow3|(k+q)\Rightarrow24|(p^2-q^2)$

Задача 4

(a) $11^{p^2}\equiv1(mod p^2)$

$\varphi(p^2)=p(p-1)$

$11^{\varphi(p^2)}\equiv1(mod p^2),\ (11,p^2)=1$

$11^{p^2}\equiv11^{\varphi(p^2)+p}\equiv11^p(mod p^2)$

$\Rightarrow11^p\equiv1(mod p^2)$

$\Rightarrow p\neq11;\ k.\varphi(p^2)=p$

$k(p^2-p)=p$

$k(p-1)=1$

$p=1+\frac{1}{k}\in\mathbb{P}\Rightarrow \fbox{p=2}$

(Ако $p=11\Rightarrow11^{121}\equiv0(mod121)\Rightarrow p=11$ не е решение)

Подусловие б) би трябвало да се решава по подобен начин, най-малкото отново да се използва Теоремата на Ойлер, но аз се затруднявам.

[chef_georg]

Благодаря много!

[Добромир Глухаров]

По отношение на Четвърта задача, очевидно имам грешка - виж ТОВА РЕШЕНИЕ.

[chef_georg]

Реших и двата примера. Моите отговори съвпадат с тези на примера, който сте ми посочил.

[silvipl]

Здравейте, опитвам се да реша подобна на първа задача, но някъде греша. Благодаря.
3^{2030014717}

[Добромир Глухаров]

$3.(-19)^9=3.(-6859)^3\equiv3.(-59)^3\equiv\cdots\equiv-37\equiv63(mod100)$

Просто при степенуване на нечетна степен знакът на основата се запазва.