если 3|phi(n)...

[maxal]

Доказать, что если $3\mid\varphi(n)$ (функция Эйлера), то

$$|\{ k:1\leq k<\frac{n}{3},\ (k,n)=1\}| = \frac{\varphi(n)}{3}.$$

[juna]

Особо просто это доказывается для случая:
$3|n \wedge ord_3(n)>1\Rightarrow (k,n)=1 \wedge 1 \leqslant k \leqslant \frac{n}{3} \Rightarrow (k+\frac{n}{3},n)=1 \wedge (k+\frac{2n}{3},n)=1$
поскольку всего взаимнопростых ровно $\varphi(n)$, то в промежутке $[1,\frac{n}{3}]$ их будет ровно одна треть.
Если $3\not | n$, т.е. для того, чтобы $3| \varphi(n)$ нужно $3|(p-1)$, где $p$ - некоторый простой делитель $n$ - нужно колдовать с периодами.

[Gordmit]

Артамонов Ю.Н. писал(а):

нужно колдовать с периодами.

Что это значит?

[RIP]

Если $9|n$, то решение написано. Поэтому дальше считаем, что $9\nmid n$. Тогда $n$ имеет простой делитель $p\equiv1\pmod3$. Обозначим $N=\lceil\frac n3\rceil-1$. Имеем

$$\#\{1\leqslant k<\frac n3\mid(k,n)=1\}=\sum_{k=1}^N\sum_{d|(k,n)}\mu(d)=\sum_{d|n}\mu(d)\left\lfloor\frac Nd\right\rfloor=$$

Далее,

$$m=\left\lfloor\frac Nd\right\rfloor\quad\Leftrightarrow\quad m\leqslant\frac Nd<m+1\quad\Leftrightarrow\quad md+1\leqslant\left\lceil\frac n3\right\rceil<md+d+1\quad\Leftrightarrow\quad$$

$$\quad\Leftrightarrow\quad md<\frac n3\leqslant md+d\quad\Leftrightarrow\quad m<\frac n{3d}\leqslant m+1\quad\Leftrightarrow\quad m=\left\lceil\frac n{3d}\right\rceil-1$$

Продолжаем

$$=\sum_{d|n}\mu(d)\left(\left\lceil\frac n{3d}\right\rceil-1\right)=\sum_{d|n}\mu(d)\left\lceil\frac n{3d}\right\rceil$$

Поэтому

$$\#\{1\leqslant k<\frac n3\mid(k,n)=1\}-\frac{\varphi(n)}3=\sum_{d|n}\mu(d)\left(\left\lceil\frac n{3d}\right\rceil-\frac n{3d}\right)$$

Из-за наличия $\mu(d)$ суммировать можно только по бесквадратным $d$. Такие делители можно разбить на пары вида $d$ и $d'=pd$, где $(d,p)=1$. Тогда $\frac n{d'}\equiv \frac nd\pmod3$, следовательно, $\left\lceil\frac n{3d}\right\rceil-\frac n{3d}=\left\lceil\frac n{3d'}\right\rceil-\frac n{3d'}$.
Поскольку $\mu(d')=-\mu(d)$, то последняя сумма равна 0. ЧТД

[maxal]

Ага.

Вторая часть:
Докажите, что

$$|\{ k:1\leq k<\frac{n}{3},\ (k,n)=1\}| = \frac{\varphi(n)+c(n)}{3},$$

где $c(n)=0,$ если $3\mid\varphi(n);$
если же $3\not{\mid}\varphi(n),$ то $c(n)=(-1)^{t+k_1+\dots+k_m} 2^{m-1},$ где $n=3^t p_1^{k_1}\dots p_m^{k_m}$ (здесь каждое простое $p_i\equiv 2\pmod{3}$ и $t\leq 1$).

[RIP]

Забыли добавить, что $n\ne1,3$, т.е. $m\ge1$.

Добавлено спустя 1 час 17 секунд:

Для $n>1$ выше была выведена формула

$$c(n)={\sum_{d|n}}'\mu(d)\left(3\left\lceil\frac n{3d}\right\rceil-\frac nd\right)$$

Штрих означает, что суммируем лишь по бесквадратным $d$.
Для $n=1$ определим $c(n)$ этой же формулой, т.е. положим $c(1)=2$.
Если $n=3n_1$, то делители имеют вид $d_1$ и $3d_1$, где $d_1|n_1$. Достаточно суммировать лишь по $d=3d_1$. Тогда

$$c(n)={\sum_{d_1|n_1}}'\mu(3d_1)\left(3\left\lceil\frac {n_1}{3d_1}\right\rceil-\frac {n_1}{d_1}\right)=-c(n_1)$$

Далее $t=0$.
Пусть $n=p^kn_1,(p,n_1)=1,p\equiv2\pmod3$.
Тогда

$$c(n)={\sum_{d|n_1}}'\mu(d)\left(3\left\lceil\frac {n}{3d}\right\rceil-\frac {n}{d}\right)-{\sum_{d|n_1}}'\mu(d)\left(3\left\lceil\frac {n}{3pd}\right\rceil-\frac {n}{pd}\right)$$

Далее,

$$3\left\lceil\frac x3\right\rceil-x=\begin{cases} 2,&x\equiv1\pmod3,\\ 1,&x\equiv2\pmod3. \end{cases}$$

Если $k$ нечетно, то

$$c(n)={\sum_{d|n_1}}'\mu(d)\left(3-3\left\lceil\frac {n_1}{3d}\right\rceil+\frac {n_1}{d}\right)-{\sum_{d|n_1}}'\mu(d)\left(3\left\lceil\frac {n_1}{3d}\right\rceil-\frac {n_1}{d}\right)=3[n_1=1]-2c(n_1)$$

Если $k$ четно, то

$$c(n)={\sum_{d|n_1}}'\mu(d)\left(3\left\lceil\frac {n_1}{3d}\right\rceil-\frac {n_1}{d}\right)-{\sum_{d|n_1}}'\mu(d)\left(3-3\left\lceil\frac {n_1}{3d}\right\rceil+\frac {n_1}{d}\right)=2c(n_1)-3[n_1=1]$$

Индукцией по $m$ получаем утверждение.

[maxal]

RIP писал(а):

Забыли добавить, что $n\ne1,3$, т.е. $m\ge1$.

Да, конечно.

И вот еще третья часть задачи, которая также относится к случаю $3|\varphi(n).$ В этом случае (целочисленный) интервал $(0,n)$ разбивается на 3: $(0,\frac{n}{3}),\ (\frac{n}{3},\frac{2n}{3})$ и $(\frac{2n}{3},n),$ в каждом из которых одно и то же количество целых чисел взаимно-простых с $n$. При этом между интервалами $(0,\frac{n}{3})$ и $(\frac{2n}{3},n)$ можно установить естественную биекцию $x\mapsto n-x,$ которая переводит взаимно-простые c $n$ числа из одного интервала в другой (и, таким образом, доказывает равенство их количеств в этих интервалах).
Задача: установить аналогичную биекцию между интервалами $(0,\frac{n}{3})$ и $(\frac{n}{3},\frac{2n}{3}).$
Для случая $9|n$ это фактически сделал Артамонов Ю.Н. (биекция $x\mapsto x+\frac{n}{3}$), так что можно ограничиться случаем $9\not|n.$

[juna]

Gordmit писал(а):

Артамонов Ю.Н. писал(а):

нужно колдовать с периодами.

Что это значит?

Вообще-то, я имел в виду, что указанную биекцию можно получать по любому простому, порядок которого выше единицы, т.е.
$n=p_1^{a_1} p_2^{a_2}...p_m^{a_m}\Rightarrow $
$\forall p_i, a_i>1:1\leqslant k\leqslant \frac{n}{p_i},(k,n)=1\Rightarrow (k+\frac{2n}{p_i},n)=1...(k+\frac{(p_i-1)n}{p_i},n)=1$
Я думал, что это поможет доказательству случая, когда $9\not | n$.
Но здесь и так уже все решено.

[maxal]

Артамонов Ю.Н. писал(а):

Но здесь и так уже все решено.

Не все. Третья часть задачи пока остается без ответа.

[RIP]

maxal писал(а):

Артамонов Ю.Н. писал(а):

Но здесь и так уже все решено.

Не все. Третья часть задачи пока остается без ответа.

Случай $\bigl|n\bigr|_3=\frac13$ легко сводится к случаю $(n,3)=1$. А вот тут что-то ничего путного в голову не приходит.

[juna]

А мне непонятно как поступать , если $3\not |n$, ведь строго на три интервала разбить не удается, т.е. нужно принимать какое-то соглашение.
Поэтому будем рассматривать случай $3|n$, $9\not |n$. В этом случае можно высказать следующую идею.
Во-первых, для того чтобы $3|\varphi(n)$ необходимо, чтобы $3|(p-1)$, где $p$ - некоторый простой делитель $n$. Пусть в промежутке $[1,\frac{n}{3}]$ мы нашли все $k$, что $(n,k)=1$. Тогда рассмотрим случаи:
$\frac{n}{3}\equiv 2 \mod 3 \wedge k\equiv 2 \mod 3 \Rightarrow k\mapsto k+\frac{n}{3}$
$\frac{n}{3}\equiv 2 \mod 3 \wedge k\equiv 1 \mod 3 \Rightarrow k\mapsto lk+\frac{n}{3}$, где $l$ может быть взято $3$ или любое число, которое не делит число $\frac{n}{3}$, например, $l=2$ если $2\not |n$
аналогично
$\frac{n}{3}\equiv 1 \mod 3 \wedge k\equiv 1 \mod 3 \Rightarrow k\mapsto k+\frac{n}{3}$
$\frac{n}{3}\equiv 1 \mod 3 \wedge k\equiv 2 \mod 3 \Rightarrow k\mapsto lk+\frac{n}{3}$.
Только вот иногда мы будем вылезать за границы интервала $[\frac{n}{3},\frac{2n}{3}]$. Поэтому здесь есть еще о чем подумать.

[maxal]

Артамонов Ю.Н. писал(а):

А мне непонятно как поступать , если $3\not |n$, ведь строго на три интервала разбить не удается, т.е. нужно принимать какое-то соглашение.

По интервалами понимается их целочисленная внутренность или даже только те целые, что взаимно-просты с $n.$ Другими словами, нужно найти биекцию между множествами
$\{ k\mid 0< k<\frac{n}{3},\,gcd(k,n)=1\}$ и $\{ k\mid \frac{n}{3}< k< \frac{2n}{3},\,gcd(k,n)=1\}.$

[juna]

maxal, а может уже пришло время раскрыть тайну биекции?

[Руст]

Если n делится на 3, то x-->x+n/3 дает соответствие при n>3. Когда n не делится на 3, то все взаимно простые с n из интервала (0,n/3) равно количеству всех взаимно простых остатков, делящихся на 3. Если это количество x0, а остатков равных 1 по модулю 3 x1, то x2=x1 (через дополнение) и $x0+2x1=3m=\phi (n)$. Учитывая, что все числа из интервала (2n/3,n) (их количество так же равно m по дополнению) отображением x-->3x-2n отобразится x1 или x2, а из интервала (n/3,2n/3) отображением x-->3x-n отобразится в x2 или x1, что доказывает равенство всех и даёт взаимно однозначное соответствие.
Вообще это верно и для любого простого делителя p $p|\phi(n)$. Соответствие такое же.
Вообще то в случае, когда 3|n, но n не делится на 3 надо соответствие x-->x+n/3 провести более аккуратно.

[RIP]

Руст писал(а):

Если n делится на 3, то x-->x+n/3 дает соответствие при n>3.

Это отображение не дает соответствия (при $9\nmid n$)

Добавлено спустя 3 минуты 7 секунд:

Но оно сводит случай $3|n$ к случаю $3\nmid n$