теория на числата задача

[ERRRY]

зад 1 .m=4
n=2^m*7^k
fi(n)=2^m*3 тази я реших и получих че k=1. Вярна ли е?
зад2. a=238^2025 b=100+m r=? от делението на a и b?

[Гост]

Някой може ли да помогне?

[ammornil]

Аз не разбирам какво се иска в тези условия. Ойлерови функции ли са това?$\\[12pt]$

Скрит текст: покажи

$\varphi(n)= 2^{m}\cdot{7^{k}}\cdot{\dfrac{1}{2}}\cdot{}\dfrac{6}{7}= 2^{m}\cdot{3} \Rightarrow 7^{k}=7 \Leftrightarrow k=1$

[ammornil]

За втората задача, $$ \begin{array}{c} a= 238^{2025} \\ b= 100 +m \end{array},\quad a\mod b =r =? $$ Това ли е цялото условие?

Правилно ли съм разчел, че $r$ е остатъкът от целочисленото деление на $a$ и $b$? Ако е така, няма как да се даде обща форма за решение, защото има много разновидности в зависимост от стойността на $m$.

[Гост]

m=4 тоест b=104

[ammornil]

$$ \begin{array}{c} a= 238^{2025} \\ b= 104 \end{array},\quad a\mod b =r =? $$ $\\[12pt] 238\mod 104 = (2\cdot{104} +30)\mod 104 \Rightarrow r= 238^{2025}\mod{104} = 30^{2025} \mod{104}\\ \text{НОД(30, 104)} \ne{1} \Rightarrow$ Теорема на Ойлер не е директно приложима.$\\[12pt] 104= 8\cdot{13} \\[12pt] 30 \equiv 6 \mod{8} \Rightarrow 30^{2025} \equiv 6^{2025} \mod{8}; \quad 6^{3}\equiv 0 \mod{8} \Rightarrow 6^{n}\equiv 0 \mod{8}, \forall{n}\in\mathbb{N}, n\geq{3} \\[6pt] \quad \Rightarrow \boxed{30^{2025}\equiv 0 \mod{8}} \\[12pt] 30 \equiv 4 \mod{13} \Rightarrow 30^{2025} \equiv 4^{2025} \mod{13};\quad \nexists{n}\in\mathbb{N} \rightarrow 4^{n}\equiv 0 \mod{13} \\[6pt] \\[6pt] \quad \varphi(13)=13\cdot{\dfrac{12}{13}}= 12 \Rightarrow 4^{12}\equiv 1 \mod{13} \\[6pt] \quad 2025 = 168\cdot{12} +9 \Rightarrow 4^{2025} \equiv 4^{9} \mod{13}, 4^{9}\equiv 12 \mod{13} \Rightarrow 4^{2025}\equiv 12 \mod{13} \\[6pt] \quad \Rightarrow \boxed{30^{2025}\equiv 12 \mod{13}} \\[12pt] \begin{array}{|l} x\equiv 0\mod{8} \\ x\equiv 12 \mod {13} \end{array} \\[6pt] x=8k, k\in\mathbb{N} \Rightarrow 8k \equiv 12 \mod{13} \\[6pt] 8\cdot{k} \equiv 12 \mod{13} \Leftrightarrow k\equiv 12\cdot{8^{-1}} \mod{13} \\[6pt] 8\cdot{5} \equiv 1 \mod{13} \Rightarrow 8^{-1}\equiv 5 \mod{13} \\[6pt] 12\cdot{5} \equiv 8 \mod{13} \Rightarrow k= 13t + 8, t\in\mathbb{N}\\[12pt] x=8k =104t +64 \Rightarrow r=64$

$\\[24pt]$Използвали сме, че $\\[6pt]\small{\because{} a\equiv b \mod{c} \Rightarrow a^{n}\equiv b^{n} \mod{c}},\quad \forall{(a, b, c, n)}\in\mathbb{N} \\[6pt] \small{ \because{} a\cdot{b} \equiv 1 \mod{n} \Rightarrow a^{-1} \equiv b \mod{n} }$