Доказать, что остаток от деления числа ** простое нечётное р равен 1.

Question

Дано ответов: 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$ , опять не для всех , а только для простого числа . А она следует из теорема Эйлера.

Матов_zn (224k баллов) 02 Апр, 18

Про группу Галуа вы что-то не то написали... Имхо, совершенно бесполезные рассуждения. Что такое n? Почему там будет множитель x+1? По какой причине там что-то будет делиться на n+1? И если уж на то пошло, то малая теорема Ферма - это прямое следствие теоремы Эйлера. Причем тут грппы Галуа? Короче, ничего не понятно. Да и предыдущие рассуждения звучат в духе "я знаю, как это решать, но вам не скажу, потому что мне неохота писать". :))) Это некачественный подход :)

оставил комментарий Denik777_zn (56.6k баллов) 02 Апр, 18

Denik777_zn · Answer 1 · 2018-04-02T12:34:15+0000

Если знаете про бином Ньютона, то можно так:
$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.