перестановка вычетов по модулю p

[maxal]

Пусть $p$ - простое число вида $8k+1$ или $8k+3$. Определим функцию $f$ на множестве $\mathbb{Z}_p=\{0,1,\dots,p-1\}$ вычетов по модулю $p$:

$$f(n) = \begin{cases} 0, & \mbox{если}\ n=0;\\ -n, & \mbox{если}\ n\ \mbox{- квадратичный вычет};\\ 2n, & \mbox{если}\ n\ \mbox{- квадратичный невычет}.\end{cases}$$

Нетрудно видеть, что $f$ является биекцией (т.е. перестановкой) на множестве $\mathbb{Z}_p$ .

Определим новую перестановку $\pi$ на множестве $\mathbb{Z}_p$, которая для каждого $n=0,1,\dots,p-1$ переводит $f(n)$ в $f(n-1)+1$.
Докажите, что $\pi$ является циклом порядка $p$.

Пример. Для $p=11$ перестановка $\pi$ является циклом $(0,10,1,7,9,3,2,6,8,5,4).$

[Sonic86]

У меня получилось $\pi^n(0)+\pi^{13-n}(0) \equiv 1 (\mod 17)$, но имеет ли это отношение к задаче - ?
И еще у меня для $p=41$ не получается цикл порядка $p$: в $\pi$ есть цикл длиной 24.

[maxal]

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

И еще у меня для $p=41$ не получается цикл порядка $p$: в $\pi$ есть цикл длиной 24.

Как это? Для $p=41$ получается такой цикл длины 41:
(0,2,36,38,24,23,35,5,30,29,28,27,9,11,17,16,8,10,20,22,32,34,26,25,31,33,15,14,13,12,37,7,19,18,4,6,40,1,3,21,39)

[Sonic86]

Да, я тут ошибся.
Удалось доказать, что $(\forall x) \pi (x) \neq x$ с помощью символа Лежандра. Скажите мне, я очень далеко продвинулся ?

(соотношение по модулю имеет место для $p=8k+1$ в силу симметричности множества квадратичных вычетов относительно 0)

[Macavity]

Можно воспользоваться соотношением:
$(\frac {2}{p})=(-1)^{\frac{(p^2-1)}{8}}=\begin{cases} 1, & \mbox{если}\ p=\pm 1\ ({mod\ 8})\ \mbox,\\ -1, & \mbox{если}\ p=\pm 3\ ({mod\ 8})\ \mbox.\end{cases}$

То есть в случае когда $p= 1\ ({mod\ 8})$ число 2 - квадратичный вычет, а когда $p= 3\ ({mod\ 8})$ число 2 - квадратичный невычет.

Тогда для $p= 1\ ({mod\ 8})$ символ Лежандра для функции $f(n)$ если n - невычет:
$(\frac {2n}{p})=(\frac {2}{p})(\frac {n}{p})=1\cdot(-1)=-1$
невычет отображается в невычет.
если n-вычет:
$(\frac {-n}{p})=(\frac {-1}{p})(\frac {n}{p})=(-1)^{\frac {(p-1)}{2}}\cdot 1=1$ (вычет отображается в вычет)
Ввиду групповых свойств - $f(n)$ - биекция

для $p= 3\ ({mod\ 8})$ символ Лежандра для функции $f(n)$ если n - невычет:
$(\frac {2n}{p})=(\frac {2}{p})(\frac {n}{p})=(-1)\cdot(-1)=1$
невычет отображается в вычет.
если n-вычет:
$(\frac {-n}{p})=(\frac {-1}{p})(\frac {n}{p})=(-1)^{\frac {(p-1)}{2}}\cdot 1=-1$ (вычет отображается в невычет)
Ввиду групповых свойств - $f(n)$ - тоже биекция

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

Определим новую перестановку $\pi$ на множестве $\mathbb{Z}_p$, которая для каждого $n=0,1,\dots,p-1$ переводит $f(n)$ в $f(n-1)+1$.
Докажите, что $\pi$ является циклом порядка $p$

Вообще и $f(n)$ и $f(n-1)+1$ являются биекциями, а $\pi$ композиция из прямой и обратной функции и следовательно тоже биекция - это и доказывает утверждение. Или что-то не так? Как по мне вместо $f(n-1)+1$ можно взять $\varphi_{a,b}(n)=f(n-a)+b$...

[maxal]

Macavity в сообщении #221164 писал(а):

Вообще и $f(n)$ и $f(n-1)+1$ являются биекциями, а $\pi$ композиция из прямой и обратной функции и следовательно тоже биекция - это и доказывает утверждение.

Это доказывает лишь, что $\pi$ является перестановкой на множестве вычетов по модулю $p$ (что собственно уже было указано в исходном сообщении). А нужно доказать, что она представляет собой не просто перестановку, а единый цикл длины $p$.