Hi everyone!
I need some help with the problem 2147G - Modular Tetration. 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 \lt 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.
(Today I learned that $$$rad$$$ stands for radical ...)
(UPD: see corrected version below, it's not true that $$$cnt(x)=\varphi(x)$$$ ...)
Isn't $$$cnt(x) = \varphi(x)$$$ only true for odd prime powers?
Oh you're totally right, and now I don't know where that first equality in the analysis is coming from ...
But the conclusion should still be true via a different series of equalities (hopefully making sense this time?). I am going to avoid using $$$\text{cnt}$$$ here because I think it only introduces confusion ...
Here let
Then
The second equality holds by CRT and LCM of orders. The third equality holds for odd $$$p_i$$$ due to the existence of a primitive root modulo $$$p_i^{e_i}$$$, and $$$p_i=2$$$ via a separate argument.
(Note: I don't think $$$\gcd(k,m)=1$$$ is required anywhere in this argument.)
Thank you so much! I finally got it
I also see that all these formulas converge to $$$k' = \Pi q_i^{\beta_i}$$$. Is this connected to the fact that $$$x^{k'} = 1 (mod m)$$$ has exactly $$$k'$$$ solutions? And for which $$$k'$$$ does this work, since $$$m$$$ arbitrary modulo. I'm still interested in how you derive the first step though :)
When $$$m$$$ is an odd prime power, this holds for all $$$k'|\varphi(m)$$$.
For general $$$m$$$, it doesn't necessarily hold for all $$$k'|\varphi(m)$$$, but it always holds when $$$k'=\text{keep}(\varphi(m),k)$$$ for some $$$k$$$.
Auto comment: topic has been updated by Noobish_Monk (previous revision, new revision, compare).