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

[Руст]

RIP писал(а):

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

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

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

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

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

Да. Именно это я имел в виду, что надо более аккуратно, т.е. разделяя дающие остаток при делении на 3 1 с остатками, дающими 2.

[RIP]

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

x2=x1 (через дополнение)

А нельзя ли поподробнее? Какое дополнение?

Кроме того, насколько я понял, Вы установили соответствие между числами интервала $(0;n/3)$ и $X_0$, а также между $(n/3;2n/3)$ и $X_j$ ($j=1$ или $2$). Но как установить соответствие между $X_0$ и $X_j$?

[Руст]

Если n даёт остаток при делении на 3 остаток j. То дополнение даёт соответствие $X_0\to X_j$. Если вначале перейти из интервала (0,n/3) к (2n/3,n) соответствием x-->n-x, и умножить на 3 по модулю n, то получим то же соответствие, т.е это ничего не даёт. Так что я ошибся.
Можно решать задачу через суммы степеней всех взаимно простых с n чисел в соответствующих интервалах. Я как то здесь демонстрировал этот метод. Количество по модулю n (сумма нулевых степеней) выражается через суммы первых степеней, делённых на n. Так получается для (n,6)=1, что в каждой одной шестой части количество взаимно простых одинаково, при условии делимости phi(n) на 6. А при делении на 12 уже может ни в каждом интервале 1/12 часть. Однако в интервалах (n/6,n/4),(n/4,n/3) и симметричных, точно 1/12 часть.

[maxal]

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$).

Задача 4. Выведите и докажите аналогичную формулу для

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