2^n ≡ 1 (mod 5^5)

от **Diadora** » 12 Авг 2017, 08:47

да се намери n - най малкото естествено число при
2^n ≡ 1 (mod 5^5)

Съгласно Теорема на Ойлер трябва да изчислим Функция на Ойлер $\varphi(n)$ при $n=5^5$.

$\varphi(p_1^{k_1}.p_2^{k_2}...p_n^{k_n})=(p_1-1)p_1^{k_1-1}.(p_2-1)p_2^{k_2-1}...(p_n-1)p_n^{k_n-1}$

$\varphi(5^5)=(5-1).5^{(5-1)}=4.5^4=2.5.2.5.25=2500$

$2^{2500}\equiv 1(mod\ 5^5)$

от **Diadora** » 13 Авг 2017, 09:18

Благодаря ви много за помоща

от **KalinaM** » 15 Авг 2017, 23:09

А кое гарантира, че n=2500 е най-малкото число?
не трябва ли да се докаже и че 2 е примитивен корен по модул 5^5?
не съм сигурна, питам...

Най-големият общ делител на $2$ и $5^5$ е $1$ - $(2,5^5)=1$. Следователно Функцията на Ойлер ни дава най-малкия степенен показател, за който е изпълнено сравнението. Поне аз така знам но, разбира се, може да бъркам.

2^n ≡ 1 (mod 5^5)

2^n ≡ 1 (mod 5^5)

Re: 2^n ≡ 1 (mod 5^5)

Re: 2^n ≡ 1 (mod 5^5)

Re: 2^n ≡ 1 (mod 5^5)

Re: 2^n ≡ 1 (mod 5^5)

Кой е на линия