# When and why does this divide?

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.

• where does your $\prod_{p | n} gcd(p-1,n-1)$ comes from ? (and writing that $rad(n) = \prod_{p | n} p$ can be helpful for the reader...) – reuns May 18 '16 at 20:51
• @user1952009 Checking my formula against known sequences in the oeis, it seems to equal this product. The product is given on the oeis. I'm trying to prove this, which I can do if I know when the division in my question occurs. I will edit that. – e2theipi2026 May 18 '16 at 20:54
• on OEIS in general there are some explanations on where the sequence and the formulas come from. so give the link where this product appears.. – reuns May 18 '16 at 20:56
• @user1952009 A063994 is the sequence for the product. – e2theipi2026 May 18 '16 at 20:59
• The sum counts the bases for which $n$ is a Fermat-pseudoprime [unless $n$ is prime, in which case the sum is $n-1$ by Fermat's theorem]. Now write $n$ as a product of prime powers, and count how many bases (modulo $p^k$) there are such that $j^{n-1} \equiv 1 \pmod{p^k}$. Use the Chinese remainder theorem to get the right hand side. – Daniel Fischer May 18 '16 at 21:03

## 1 Answer

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.

• Thank you. You are the only one who answered my question. – e2theipi2026 May 18 '16 at 21:24
• what is the argument for "the number of solutions for $x^{n-1} = 1$ in $G$ is $gcd(n-1,|G|)$" ? considering a group homomorphism $x \to x^{n-1}$ since $G$ is abelian ? – reuns May 18 '16 at 21:29
• @user1952009 Are you claiming that the comment on the page, "a(n) = number of bases b mod n for which b^{n-1} = 1 mod n." is incorrect? Because if it is correct, then replace j with b in my sum. This counts those bases b mod n for which b^{n-1} = 1 mod n. If it is incorrect, then I am following my equation from something already wrong on the oeis. – e2theipi2026 May 18 '16 at 21:42
• @user1952009 It's important that $G$ is cyclic [for odd $p$; for $p = 2$ we use that we have a $2$-group], not just abelian. Let $g$ be a generator of the group. We have $(g^m)^{n-1} \equiv 1 \pmod{p^k}$ if and only if $(p-1)p^{k-1} \mid m\cdot (n-1)$. That is the case if and only if $\frac{p-1}{\gcd(p-1,n-1)}\cdot p^{k-1} \mid m$. – Daniel Fischer May 18 '16 at 21:47
• As a note, this comment is proved in "Lucas pseudoprimes Robert Baillie and Samuel S. Wagstaff. Math. Comp. 35 (1980), 1391-1417 ", page 3. So if this proof is correct, then my sum is too. So, its already proved! I was in a sense looking for another one. So, I did not just throw an equation on oeis without reason. That claim is insulting. – e2theipi2026 May 18 '16 at 22:22