Hi everyone!↵
↵
I need some help with the problem [problem:2147G]. In the editorial there is this identity↵
↵
$\sum_{x|\varphi(m), rad(x) | k} cnt(x) = \sum_{d_1| q_1^{\beta_1}, \ldots , d_t | q_t^{\beta_t}} \prod \varphi(d_i)$↵
↵
Where $k$ is a square-free number with $gcd(k, m) = 1$ and $k | \varphi(m)$. $cnt(x)$ is the number of remainders $1 \le a < m$ for which $ord_m(a) = x$. $k = q_1 q_2 \ldots q_t$ and $\beta_i$ is the exponent of $q_i$ in $\varphi(m)$↵
↵
It is some counting in 2 ways, as far as I understand. I tried to prove this for several days, now I am desperate to know the proof since the editorial mentions this as something obvious and the author of the problem doens't respond.
↵
I need some help with the problem [problem:2147G]. In the editorial there is this identity↵
↵
$\sum_{x|\varphi(m), rad(x) | k} cnt(x) = \sum_{d_1| q_1^{\beta_1}, \ldots , d_t | q_t^{\beta_t}} \prod \varphi(d_i)$↵
↵
Where $k$ is a square-free number with $gcd(k, m) = 1$ and $k | \varphi(m)$. $cnt(x)$ is the number of remainders $1 \le a < m$ for which $ord_m(a) = x$. $k = q_1 q_2 \ldots q_t$ and $\beta_i$ is the exponent of $q_i$ in $\varphi(m)$↵
↵
It is some counting in 2 ways, as far as I understand. I tried to prove this for several days, now I am desperate to know the proof since the editorial mentions this as something obvious and the author of the problem doens't respond.
