Zadanie ze starej OM

mikolajm · Post autor: **mikolajm** » 29 sty 2006, o 21:06

Mam tu takie zadanko z XXI OM, z którym nie za bardzo sobie radzę. Gdyby ktoś mógł pomóc...

Udowodnić, że dla każdego nieparzystego i większego od 1 \(\displaystyle{ a}\) istnieje takie naturalne \(\displaystyle{ b < a}\), że \(\displaystyle{ 2^{b}-1}\) dzieli się przez \(\displaystyle{ a}\).

Z góry dzięki za pomoc.

tomek09876 · Post autor: **tomek09876** » 29 sty 2006, o 21:38

skorzystaj z twierdzenia Eulera

mikolajm · Post autor: **mikolajm** » 29 sty 2006, o 22:13

Hmmm... Sprytne. Szkoda, że nie znałem tego twierdzenia wcześniej, wtedy zadanie byloby oczywiste. Dzięki wielkie.

Tylko zastanawia mnie, dlaczego pan Pawłowski umieścił to zadanie w dziale o zasadzie szufladkowej Dirichleta... Czy ktoś móglby przedstawić rozwiązanie wykorzystujące (nie wiem w jakim stopniu) tę zasadę?

tomek09876 · Post autor: **tomek09876** » 29 sty 2006, o 22:38

oczywiscie da sie bardzej elementarnie
trzeba rozpatrzec a-1 liczb,kolejnych poteg liczby 2, a pozniej skorzystac z zasady szufladkowej Dirichleta.

Z jakiej ksiazki jest to zadanie??

mikolajm · Post autor: **mikolajm** » 29 sty 2006, o 22:44

"Kółko matematyczne dla olimpijczyków".