I've been working a lot with forms of this type, $\lfloor\frac{f}{g}\rfloor-\lfloor\frac{f-1}{g}\rfloor=1$ if $g|f$ and $0$ otherwise. This is valid for any expression $f$ and $g$ of natural numbers provided $g$ is nowhere $0.$ I can count these divisions in a sum and use this to find other representations of number theoretic functions. For example,
$\sum_{j=1}^{n}\lfloor\frac{j^n}{n}\rfloor-\lfloor\frac{j^n-1}{n}\rfloor=\frac{n}{rad(n)}.$
Where $rad(n)$ is the product of distinct prime factors of $n.$
Which I can show by proving that $n$ can only divide $j^n$ if $j$ is a multiple of $rad(n).$ Now I have the following relationship to prove and this is where I am stuck.
$\sum_{j=1}^{n}\lfloor\frac{j^{n-1}-1}{n}\rfloor-\lfloor\frac{j^{n-1}-2}{n}\rfloor=\prod_{p|n}\gcd(p-1,n-1).$
This tells me that there must be a reason that when $n|(j^{n-1}-1),$ the count of these divisions $\le n$ gives the product on the right side. Does anyone have a reason or explanation why and when $n|(j^{n-1}-1)$ for $1\le j \le n.$ Any help on this is appreciated, its not clicking with me.
Let $p$ be a prime dividing $n$, and $k$ the exponent of $p$ in the prime factorisation of $n$. Suppose first that $p$ is odd. The group of units in $\mathbb{Z}/(p^k)$ is cyclic of order $(p-1)p^{k-1}$, and therefore there are $\gcd(n-1,(p-1)p^{k-1}) = \gcd(n-1,p-1)$ elements in that group with $a^{n-1}\equiv 1 \pmod{p^k}$. If $p = 2$, then the group of units in $\mathbb{Z}/(2^k)$ is cyclic of order $2^{k-1}$ if $k \in \{1,2\}$, and a direct product of a cyclic group of order $2$ with a cyclic group of order $2^{k-2}$ if $k \geqslant 3$. In any case, every element of that group has an order that is a power of $2$, and since $n-1$ is odd if $2\mid n$, there is only one element of that group with $a^{n-1} \equiv 1 \pmod{2^k}$ (namely the residue class of $1$), and $1 = \gcd(n-1,2-1)$.
Combining the solutions of $a^{n-1} \equiv 1 \pmod{p^k}$ for all $p\mid n$ then shows there are
$$\prod_{p \mid n} \gcd(n-1,p-1)$$
numbers $j \in \{1,\dotsc,n\}$ with $n \mid j^{n-1}-1$, which the sum counts.