Thực ra bài này mà nói ý tưởng thì ra hết mình làm luôn cho bạn
Xét định lý $Euler$ với $gcd(a,m)=1$ ta sẽ chứng minh $a^{\phi (m)}\equiv 1(modm)$
Xét hệ thặng dư thu gọn $module$ của $m$ là $A={a_{1},a_{2},...........a_{\phi (m)}}$
Hiển nhiên do $gcd(a,m)=1$ nên hệ $B={aa_{1},.....aa_{\phi (m)}}$ cũng là một hệ thặng dư thu gọn $mod m$
Do đó nhân hai vế ta có đpcm
Với định lý $Fermat$ vì $m$ nguyên tố nên $\phi (m)=m-1$ ta có đpcm
Cho em hỏi: Trong đa số các trường hợp thì định lý euler vẫn đúng với trường hợp hai số không phải là nt cùng nhau.
áp dụng vào bài tìm dư, ví dụ:tìm dư của $2468^{1008}:136$ (một bài ngẫu nhiên trong đống bài tập)
rõ ràng nếu áp dụng thẳng đl euler mà không tách thì:
$\Phi 136=64$
$\Rightarrow 2468^{1008}\equiv 20^{48}\equiv 120(mod 136)$ (đáp án đúng)
tuy nhiên trong một số bài thì áp dụng trực tiếp không đúng, cho em hỏi trong trường hợp nào thì không sử dụng trực tiếp được anh nhỉ?
em mong có câu trả lời as soon as possible
(tuy không muốn làm anh phật ý nhưng em đang cần rất gấp câu trả lời, mong anh thông cảm, thứ 3 nay em đi thi rồi)