Как се доказва делимостта на едно число

[skidrow]

Здравейте драги съфорумци! Имам следния въпрос: как се доказва делимост на едно число с друго?
Например следната задача: "Да се докаже че числото [tex]12^{198} - 3^{48}[/tex] се дели на 13."

Някакви идеи?

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

Трябва да докажем, че:

[tex]12^{198}-3^{48}\equiv 0(mod\ 13)[/tex]

Доказателство:

[tex]\varphi(13)=\varphi(13^1)=13^1-13^0=13-1=12[/tex]

[tex]\Rightarrow\ 12^{k.\varphi(13)}\equiv 12^{12k}\equiv 1(mod\ 13)[/tex]

[tex]198=12.16+6\Rightarrow\ 12^{198}\equiv 12^6(mod\ 13)[/tex]

[tex]3^{k.\varphi(13)}\equiv 3^{12k}\equiv 1(mod\ 13)[/tex]

[tex]48=4.12\Rightarrow\ 3^{48}\equiv 1(mod\ 13)[/tex]

[tex]\Rightarrow\ 12^{198}-3^{48}\equiv 12^6-1\equiv (12^3+1)(12^3-1)\equiv 1729.1727\equiv 0.(-2)\equiv 0(mod\ 13)[/tex]

Може да използваш следния теоретичен материал: http://www.math10.com/forumbg/viewtopic.php?t=2779

Само началото, по-нататък теорията е по-скоро за студенти .

[grav]

Moje i da zabelejish, che

[tex]12\equiv -1(\text{mod}\ 13)[/tex]

[tex]12^{198}\equiv (-1)^{198}\equiv 1(\text{mod}\ 13)[/tex]

[skidrow]

Разбрах как става. Благодаря за отговорите!

[pspeeva]

[tex]12^{198}-3^{48}=[/tex]
[tex]=(13-1)^{198} - 3^{48}=[/tex]
[tex]=.........+ 1^{198} - 3^{48}[/tex]

на мястото на точките са събираеми, които съдържат множител 13 ( А.[tex]13^n.1^k[/tex], където A=n над k) , а тези двете останаха, че не се делят на 13. И сега, използвайки разлагане чрез разлика на квадрати

[tex]1^{48} - 3^{48}=(1^{24}+3^{24})(1^{12} + 3^{12})(1 + 3^6)(1 + 3^3)(1 - 3^3)[/tex]
и това последното е -26, значи се дели на 13 и ...

Това добре, обаче със следващата задача този подход не е много подходящ, че се получават едни големи числа.
[tex]4^{60} - 62^{48}[/tex]--->дали се дели на 7
По горния ми метод трябва да се докаже, че или [tex]4^{60} - 1[/tex],или [tex]3^{60} - 1[/tex] се дели на 7. Ако се използва разлагане, се налага да се пресмята 3 или 4 на 10 степен.