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,


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.


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.

  • $\begingroup$ 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...) $\endgroup$ – reuns May 18 '16 at 20:51
  • $\begingroup$ @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. $\endgroup$ – e2theipi2026 May 18 '16 at 20:54
  • $\begingroup$ 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.. $\endgroup$ – reuns May 18 '16 at 20:56
  • $\begingroup$ @user1952009 A063994 is the sequence for the product. $\endgroup$ – e2theipi2026 May 18 '16 at 20:59
  • 1
    $\begingroup$ 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. $\endgroup$ – Daniel Fischer May 18 '16 at 21:03

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.

  • $\begingroup$ Thank you. You are the only one who answered my question. $\endgroup$ – e2theipi2026 May 18 '16 at 21:24
  • $\begingroup$ 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 ? $\endgroup$ – reuns May 18 '16 at 21:29
  • $\begingroup$ @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. $\endgroup$ – e2theipi2026 May 18 '16 at 21:42
  • 1
    $\begingroup$ @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$. $\endgroup$ – Daniel Fischer May 18 '16 at 21:47
  • $\begingroup$ 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. $\endgroup$ – e2theipi2026 May 18 '16 at 22:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.