Задача за делимост

[LazyWorker]

Да се докаже че 4^121 + 7^121 се дели на 11^3.
Някой знае ли как се решава?

[kucheto]

Задачата е директно следствие на следната теорема:
Ако [tex]p[/tex] е нечетно просто число и е изпълнено [tex](x,p)=(y,p)=1,\ p|x+y[/tex] и [tex]n[/tex] е нечетно, имаме, че [tex]v_p(x^n+y^n)=v_p(x+y)+v_p(n),[/tex] където [tex]v_p(a)[/tex] е степента на [tex]p[/tex] в каноничното разлагане на [tex]a.[/tex]

Тази теорема се нарича на английски Lifting The Exponent Lemma (LTE) (не я съм срещал в български източници, но може би ще се преведе като "Лема за повдигане на експонентата") и хубав материал за нея можеш да намериш на http://www.artofproblemsolving.com/Reso ... rs/LTE.pdf.

В нашия случай имаме: [tex]v_{11}(4^{121}+7^{121})=v_{11}(4+7)+v_{11}(121)=1+2=3\Rightarrow 11^3|4^{121}+7^{121}.[/tex]

[pal702004]

Ако не е предвидено използването на LTE можеш да използваш бинома на Нютон. При нечетно n
[tex]7^n=(11-4)^n \equiv -C_n^2\cdot 11^2\cdot 4^{n-2}+n\cdot 11\cdot 4^{n-1}-4^n\quad \pmod {11^3}[/tex]

И при [tex]n=11^2[/tex], след събиране с [tex]4^n[/tex] останалите два члена се делят на [tex]11^3[/tex]