Найдите остаток

[rightways]

Пусть $a\in N$, $p,q>2$ простые числа такие, что $q\not|\,a-1$. Известно, что $q| a^p-1$.
Найдите остаток

$$(1+a)(1+a^2)\cdots (1+a^{p-1})\equiv \,? \! \pmod q$$

[kotenok gav]

Как-то через $1+a^k\equiv 1+a^{p+k}$ и $1+a^p\equiv2$?

[maxal]

Пусть $f(x) : = (1+x)\cdots(1+x^{p-1})$. Его мультисекция с шагом $p$ и начальным смещением $m$ равна:

$$f_m(x) = \frac{1}{p} \sum_{j=0}^{p-1} w^{-mj} f(w^j x),$$

где $w = \exp(\frac{2\pi}p I)$ - примитивный корень степени $p$ из единицы.

Нетрудно понять, что делимость $q\mid (a^p-1)$ влечёт

$$(1+a)\cdots(1+a^{p-1}) = f(a) \equiv \sum_{m=0}^{p-1} f_m(1) a^m\pmod{q}.$$

Так как $1+w^{jk} = 2\cos(\frac{\pi jk}p)\exp(\frac{\pi jk}p I)$, то

$$f(w^j}) = \prod_{k=1}^{p-1} 2\cos(\frac{\pi jk}p)\exp(\frac{\pi jk}pI) = \begin{cases} 2^{p-1},&\text{if }j=0\\ 1,&\text{otherwise}\end{cases}$$

и поэтому

$$f_m(1) = \frac{1}{p} (2^{p-1} + \sum_{j=1}^{p-1} w^{-mj}) = \begin{cases} \frac{2^{p-1}-1}p+1,&\text{if }m=0\\ \frac{2^{p-1}-1}p,&\text{otherwise}\end{cases}$$

Итак,

$$\sum_{m=0}^{p-1} f_m(1) a^m = 1 + \frac{2^{p-1}-1}p \frac{1-a^p}{1-a}\equiv 1\pmod{q}.$$

PS. На самом деле мы доказали более общий результат, что для всякого простого $p$ выполняется следующее сравнение для полиномов:

$$(1+x)\cdots(1+x^{p-1}) \equiv 1 + \frac{2^{p-1}-1}p (1+x+\cdots+x^{p-1}) \pmod{x^p-1}.$$

В этой связи вспоминается вот эта старая задачка.

[nnosipov]

rightways в сообщении #1506754 писал(а):

Пусть $a\in N$, $p,q>2$ простые числа такие, что $q\not|\,a-1$. Известно, что $q| a^p-1$.
Найдите остаток

$$(1+a)(1+a^2)\cdots (1+a^{p-1})\equiv \,? \! \pmod q$$

В таком виде это что-то устное: остаток равен единице. (Всего лишь подставить $-1$ вместо $x$ в выражение $(x^p-1)/(x-1)$.)

-- Сб фев 27, 2021 11:46:48 --

maxal в сообщении #1506779 писал(а):

для всякого простого $p$ выполняется следующее сравнение для полиномов:

$$(1+x)\cdots(1+x^{p-1}) \equiv 1 + \frac{2^{p-1}-1}p (1+x+\cdots+x^{p-1}) \pmod{x^p-1}.$$

Вот это гораздо симпатичней.

maxal в сообщении #1506779 писал(а):

В этой связи вспоминается вот эта старая задачка
.

А это еще лучше. Удивительно, но раньше не попадалось, хотя в старые темы частенько заглядываю.

[maxal]

nnosipov в сообщении #1506784 писал(а):

В таком виде это что-то устное: остаток равен единице. (Всего лишь подставить $-1$ вместо $x$ в выражение $(x^p-1)/(x-1)$.)

Видимо, у меня забрало запотело глаз замылился. Как здесь вы переходите от исходного выражения к $\frac{x^p-1}{x-1}$?

-- Sat Feb 27, 2021 09:23:46 --

Ага, можно так.
$1+a^j$ являются различными корнями многочлена $\frac{(x-1)^p-1}{x-1-1}$ по модулю $q$, а значит их произведение равно свободному члену, что есть $1$.

-- Sat Feb 27, 2021 09:49:31 --

Кстати, аналогичный аргумент для многочленов даёт:

$$(1+x)\cdots (1+x^{p-1})\equiv 1\pmod{\Phi_p(x)}.$$

Также, тривиальным образом у нас есть сравнение:

$$(1+x)\cdots(1+x^{p-1})\equiv 2^{p-1}\pmod{x-1}.$$

Остается заметить, что $(x-1)\Phi_p(x)=x^p-1$, и применить китайскую теорему об остатках для получения результата из моего исходного решения:

$$(1+x)\cdots(1+x^{p-1})\equiv 1+\frac{2^{p-1}-1}p\Phi_p(x) \pmod{x^p-1}.$$

Получается, что привлечение мультисекций и тригонометрии было излишним.

[nnosipov]

maxal в сообщении #1506842 писал(а):

Ага, можно так.
$1+a^j$ являются различными корнями многочлена $\frac{(x-1)^p-1}{x-1-1}$ по модулю $q$, а значит их произведение равно свободному члену, что есть $1$.

Да, ровно это (с точностью до обозначений) и имелось в виду.

maxal в сообщении #1506842 писал(а):

применить китайскую теорему об остатках для получения результата из моего исходного решения

Да, ровно так (через КТО) я и сделал утром: себе записал, а сюда не выложил, поленился. У меня в такой форме получилось:

Пусть $p$ --- простое число. Тогда

$$ (t-1)(t-x)\ldots(t-x^{p-1}) \equiv t^p-1+c_p(t)(1+x+\ldots+x^{p-1}) \pmod{x^p-1} $$

в кольце $\mathbb{Z}[x]$. Здесь

$$ c_p(t)=\frac{(t-1)^p-t^p+1}{p}. $$

-- Сб фев 27, 2021 22:30:07 --

maxal в сообщении #1506842 писал(а):

Получается, что привлечение мультисекций и тригонометрии было излишним.

Возможно, мультисекции и вычисления в факторкольце по модулю многочлена $x^p-1$ друг друга заменяют. Разные точки зрения на одно явление, так сказать.

[maxal]

nnosipov, напрашивается вопрос обобщения на составные $p$.

[nnosipov]

Сходу не удалось ничего придумать (кроме того, что ответ явно должен быть другим). Наверное, надо начинать со степени простого.

[Sonic86]

Для степени простого $p>2$ формула скорее всего такая:

$$(1+x)...(1+x^{p^n-1})\equiv 1+\sum\limits_{k=1}^n\frac{2^{p^k-1}-2^{p^{k-1}-1}}{p^k}\frac{x^{p^n}-1}{x^{p^{n-k}}-1}\pmod{x^{p^n}-1}$$

[nnosipov]

Sonic86 в сообщении #1507840 писал(а):

формула скорее всего такая:

$$(1+x)...(1+x^{p^n-1})\equiv 1+\sum\limits_{k=1}^n\frac{2^{p^n-1}-2^{p^{n-1}-1}}{p^k}\sum\limits_{j=0}^{p^k-1}x^{p^{n-k}j}\pmod{x^p-1}$$

Видимо, опечатка: нужно по $\pmod{x^{p^n}-1}$. Но все равно не сходится: например, при $p=3$ и $n=2$. При $n=1$ все нормально.

[Sonic86]

Пофиксил, перепроверил

(автотест на PARI/GP)

forprime(p=3, 7, for(n=1, 4, 
m=p^n; f=Mod(1,x^m-1); 
for(k=1, m-1, f=f*(x^k+1)); 
g=Mod(1, x^m-1); 
for(k=1, n, g=g+(2^(p^k-1)-2^(p^(k-1)-1))/(p^k)*(x^(p^n)-1)/(x^(p^(n-k))-1));
  if(f!=g,print(f); print(g))
));

[Sonic86]

Для нечетных $n$:

$$(1+x)...(1+x^{n-1})\equiv \sum\limits_{d|n}\frac{x^n-1}{x^{n/d}-1}\frac{1}{d}\sum\limits_{t|d}2^{\frac{d}{t}-1}\mu(t) \pmod{x^n-1}$$

Доказывать можно подстановками $x=\exp\frac{2\pi i}{d}, d|n$

[maxal]

Sonic86, $\frac1d\sum_{t\mid d}2^{\frac{d}t}\mu(t)$ - это известная штука, см. A001037.