Отново сингапурска задача

[Пафнутий]

Да се намерят всички нечетни прости числа [tex]p[/tex], които делят [tex]\sum_{n=1}^{103} n^{p-1}[/tex]
(3 задача, Сингапурска Олимпиада по математика за определяне отбора за IMO 2007)
ПП Тази е доста по-сложна и ми отне повече време, но поне основната идея е очевидна

[Реклама]

[martosss]

Нека 103=mp+n. е ми по модул p като се разгледа се установява, че тази сума е сравнима с [tex]\underbrace{(1^p+2^p+3^p+\cdots +\left(\frac{p-1}{2}\right)^p+\left(-\frac{p-1}{2}\right)^p+\cdots +(-3)^p+(-2)^p+(-1)^p)*m}_{=0}\: +\: \underbrace{1^p+2^p+\cdots n^p}_{> 0}\ne 0[/tex] откъдето ще получим решение само при n=0, тоест [tex]p=2^k*103,\: k\in N[/tex], понеже тази сума се дели само на 2 и на 103


Сега не знам как да сложа горна граница за k(ако изобщо има такава).


Ако пък p>103, то няма такова число p, което да дели тази сума, понеже тогава става 1+2+3+4+...(p-1)/2+(-(p-1)/2)+...+(-s), s>0 и става винаги положителна


Не знам как да докажа, че в някакъв случай тази сума не може да стане равна точно на t пъти по самото число, ама .... едва ли ще стане

[Пафнутий]

Не мога да ти разбера решението? Защо делиш [tex]103[/tex] на [tex]p[/tex] с остатък. Обоснови се

[martosss]

[Baronov]

В Сингапур явно се влиза доста лесно в отбора. Тази задача ми се падна на пролетен в 10-клас и то с 2003 вместо 103. От теоремата на Ферма очевидно числото е по-малко от 103. Тук даже могат да се разгледат всички прости числа до 103. На пролетния се правеше някъв трик от който следваше, че числото е по малко от корен от 2003. Но тук даже и това не е нужно.

[Пафнутий]

[Пафнутий]

Никой ли няма идеи?
ПП Използвайте малката теорема на Ферма

[dim]

Нека [tex]A=1^{p-1}+2^{p-1}+...k^{p-1}+...+102^{p-1}+103^{p-1}[/tex]

[tex]k^{p-1}\equiv 1(mod p)[/tex], ако [tex](p,k)=1[/tex]

Следователно ако [tex]k=p.q_k+r,(r=1,0)[/tex] то [tex]A=p(q_1+q_2+...+q_k+...+q_n)+S[/tex], което значи, че ако [tex]p/A[/tex] то [tex]p/S[/tex]

[tex]S=(p-1).q+r, 103=p.q+r (0\le r\le p)[/tex], следователно [tex]S=(p-1).q+103-p.q=p.q-q+103-p.q=103-q[/tex]

Ако [tex]p>103[/tex], то [tex]S=103[/tex](защото всички остатъци по модул p са равни на 1,защото (p,k)=1,1≤k≤103).Значи за всяко [tex]p>103[/tex], A не се дели на p.

По нататък следва хамалогия.Вижда се че 3/А e единствено.
Аз разсъждавам така:
за 51≤p≤103, q=1, S=102=2.3.17, значи проверявам за p=3,17
за 37≤p≤53, q=2, S=101...


Абе нещо издиша работата и не мога да огранича простите делители, за да не прибягвам до толкова много непосредствени проверки.......със сигурност има нещо по-рацонално

[Пафнутий]

[tex]\sum_{n = 1}^{103} n^{p - 1}\equiv 0.[\frac {103}{p}] + 1(103 - [\frac {103}{p}](mod p)\Rightarrow 103\equiv[\frac {103}{p}](mod p)(1)[/tex]. Нека [tex]103=pq+r[/tex] и [tex]0\le r\le p - 1[/tex]. Тогава [tex](1)[/tex] е еквивалентно на [tex]r \equiv q(mod p)[/tex]
1случай: [tex]q<p\Rightarrow q=r[/tex] , тогава [tex]103=pr+r=r(p+1)[/tex] , но 103-просто, т.е[tex] r=1, p+1=103[/tex] -противоречие с [tex]p[/tex]- просто.
2случай [tex]q\ge p[/tex], тогава имаме [tex]103 = p.q\ge p^2[/tex] и така получаваме, че [tex]p\le\sqrt{103}[/tex] и т.е проверяваме за [tex]p=3,5,7[/tex] чрез [tex](1)[/tex]. Така достигаме, че единствено решение е [tex]p=3[/tex]
ПП За да реша тази задача, просто имах късмета преди да съм гледал подобна давана на ПМТ през 2004

[dim]

Браво! Спретнато и кратко решение

Сега като гледам съм стигнал почти до [tex]r\equiv q(modp)[/tex](това следва от [tex]S=(p-1)q+r=pq+r-q[/tex],т.е. ако [tex]p/S[/tex],то[tex]p/r-q[/tex]).Очевидно е, но не съм го забелязал.Абе важното е да си здрав