число 341 и АКС тест

[Soul Friend]

когда примитивно объясняют АКС тест, то говорят что если все биномиальные коэффициенты степени $n$ делятся на $n$, то число $n$ простое. Тогда какой свой бином.коэффициент не делит число 341, тогда как при любых $a$ $a^{341}-2$ делится на 341. Если знаете этот коэффициент, напишите пожалуйста.

[user14284]

${341\choose 11}$

[Soul Friend]

разве коэффициенты не должны быть больше степени? Ну, первый коэффициент всегда единица, второй коэффициент $\frac{341^2-341}{4}$ , третий коэф. - $\frac{341^3-341}{6}$ . четвёртый коэф. - $\frac{341(341-1)(341-2)(341-3)}{24}$. дальше не знаю как вычислять. Все они делятся на 341

[user14284]

${n\choose k}=\frac{n!}{k!(n-k)!}$

${341\choose 11}\equiv 31\pmod {341}$

[Xaositect]

Soul Friend в сообщении #1172158 писал(а):

Все они делятся на 341

Почему Вы так думаете? Там же знаменатель есть.

[Soul Friend]

а как понять $11$, это одинадцатый в строке коэффициент, или АКС тест не имеет ничего общего с пирамидой Паскаля? Сумма чисел в строке пирамиды Паскаля равна $2^n$, по краям есть единицы, отнимаем эти единицы и получаем китайскую теорему об остатках. Так, $2^n-2$ делится на 341, поэтому я допустил что все коэффициенты делятся на 341.

[user14284]

Soul Friend в сообщении #1172163 писал(а):

а как понять $11$, это одинадцатый в строке коэффициент

Да

Вы спецально выбрали 341 в качестве подопытного кролика? Почему не 4, например?

[Soul Friend]

341 нечётное число которое проходит тест Ферма как простое число, мне бы знать чему равен этот одинадцатый коэффициент в пирамиде Паскаля

[Xaositect]

Soul Friend в сообщении #1172173 писал(а):

мне бы знать чему равен этот одинадцатый коэффициент в пирамиде Паскаля

http://www.wolframalpha.com/input/?i=binomial(341,11)

[user14284]

Кстати, обратите внимание на связь: $341=11\cdot 31$ и оно не делит $ {341\choose k}$ для $k=11,22,31,33,44,55,62,66$ и т.д.

[Soul Friend]

так, значит, значение $341\choose 11$ нужно снова разделить на 341, и если нацело не делится, значит 341 составное число?

-- 27.11.2016, 19:22 --

user14284
Xaositect
Спасибо, становится яснее.