Processing math: 6%

Математикадан республикалық олимпиада, 2009-2010 оқу жылы, 11 сынып


n натурал саны үшін a^{n-1} \equiv 1 \pmod {n} салыстыруы орындалатындай және n-1 санының кез келген p жай бөлгіші үшін a^{(n-1)/p} \not\equiv 1 \pmod{n} орындалатындай a натурал саны табылатыны белгілі. Олай болса, n саны жай екенін дәлелдеңдер.
посмотреть в олимпиаде

Комментарий/решение:

  1
7 года 2 месяца назад #

Мне кажется или здесь есть опечатка.

  2
4 года 1 месяца назад #

Да, здесь опечатка. В этой задаче на русском и на казахском разные условии(в казахском правильный).

  2
4 года 1 месяца назад #

Из условия следует, что n-1 показатель числа a по модулю n. Тогда

\{a^1,\ldots,a^{n-1}\}=\{1,\ldots,n-1\},

но с другой стороны (a,n)=1, то есть числа 1,\ldots,n-1 взаимно просты с n, тогда n-простое.

  3
2 года 3 месяца назад #

Малая теорема Ферма и все