Question

Доказать, что остаток от деления числа $2^{p-1}$ на простое нечётное р равен 1.

Answer 1

Если знаете про бином Ньютона, то можно так:
$2^p=(1+1)^p=1^p+C_p^1+C_p^2+\ldots+C_p^{p-1}+1^p$
Где $C_p^k=\frac{p!}{(k)!(p-k)!}$ - биномиальный коэффициент. При всех k  кроме k=0 и k=p, числитель этого биномиального коэффциента делится на p, а знаменатель не делится, Т.к. p - простое, а само $C_p^k$ - целое, то p делит все слагаемые $C_p^k$ кроме крайних единиц. Значит остаток от деления 2^p на p равен 2. И поэтому остаток отделения $2^{p-1}$ равен 1.

Answer 2

  Если вам нужно "сухое" доказательство , то это Малая теорема Ферма , $a^{p-1} \equiv 1 \ mod p$ , у вас тут $a=2$ , и оно не делится на $p$ , откуда и следует утверждение задачи  
   
Если хотите более элементарное доказательство , можно это доказать при помощи Бинома Ньютона , или попробовать  представить просто число в виде $p=6x+1$. Но рассматривать частные случаи , что то не охота
 
Либо через группу Галуа , если это доказательство подойдет .  Если рассматривать уравнение вида $x^n-1$ ,  то есть имеет вид $(x-1)(x+1)(x^2-x+1)....$ , то найдется такое число во множители что ,$(x-1)(x+1)(x^{2(n-k)}+x^{n-k}+...1)...$ будет делится на $n+1$ , опять не для всех , а только для простого числа . А она следует из теорема Эйлера.