# What is known about certain congruences of $n$?

Let's say we are given a number, $n$. I'm interested in the special properties of all congruences of $n$ that yield $m-1 \bmod m$ for some number $m$. If we were to make a list of all $m$ that this satisfies (starting from 2), what would be the asymptotic behavior of the product of $m$'s?

Let me give an example:

Say $n$=5. Then $5\equiv 1 \pmod 2$, so the equation $(n\bmod m)=(m-1\bmod m)$ is satisfied for $m$=2, so we add 2 to the list. $5 \equiv 2\pmod 3$, so we add 3 to the list as well. This gives a product of $2\cdot 3 = 6$ for the list at $m$=3. $5\equiv 1\pmod 4$, which does not satisfy the special property, so for $m$=4, the product remains at 6. I'd like to know the asymptotic behavior of the products for a given $m$. I guess that the product will approach a maximum value as $m$ approaches $n$, but what is this value?

-
It appears that the product approaches $n+1$ for great enough $n$. I guess this may be an easy proof for someone... I was hoping it would be much greater than $n$. :-( –  Matt Groff Aug 20 '11 at 11:03
For $n$=a prime $p$-1, the product appears to be 0. –  Matt Groff Aug 20 '11 at 11:09
Wait, are you not simply looking at the product of the divisors of n+1, the integer n+1 excepted... –  Did Aug 20 '11 at 11:12
But Didier's point is the key. Try $n=29$. Your list then contains 15,10,6,5,3,2. –  Jyrki Lahtonen Aug 20 '11 at 11:26
Seems to me that for $n=5$ (which is what you meant, although you wrote $m=5$) you also get the modulus 6, since $5\mod\,6=5=6-1$. More generally, for every $n$ you get the modulus $n+1$. –  Gerry Myerson Aug 20 '11 at 12:24

Let $n\geq 1$ be a natural number. You are looking for those $m\geq 1$ such that $n\equiv m-1 \bmod m$ or, equivalently, $n\equiv -1 \bmod m$, or $n+1\equiv 0 \bmod m$. Hence, you are looking for all divisors of $n+1$.

The function whose values you are trying to calculate is $D(n) = \prod_{d|n+1} d$.

Here are the first few values of $D(n)$, for $n=1,2,\ldots,19$:

$$2,\ 3,\ 8,\ 5,\ 36,\ 7,\ 64,\ 27,\ 100,\ 11,\ 1728,\ 13,\ 196,\ 225,\ 1024,\ 17,\ 5832,\ 19,\ 8000,$$

or in a more enlightening notation...

$$2,\ 3,\ 4^{3/2},\ 5,\ 6^2,\ 7,\ 8^2,\ 9^{3/2},\ 10^2,\ 11,\ 12^3,\ 13,\ 14^2,\ 15^2,\ 16^{5/2},\ 17,\ 18^3,\ 19,\ 20^3.$$

This suggests that $D(n)$ is always a power of $n+1$. Some remarks:

• We always have that $n+1$ is a divisor of $n+1$, so $D(n)$ is divisible by $n+1$.

• The number $n+1$ is prime if and only if $D(n)=n+1$.

• If $n+1 = p^t$, where $p$ is a prime and $t\geq 1$, then

$$D(n)=\prod_{d|p^t} d = \prod_{i=0,\ldots,t} p^i = p^{\sum_{i=0}^t i} = p^{t(t+1)/2}=(n+1)^{(t+1)/2}.$$

• If $n+1=pq$, where $p$ and $q$ are distinct primes, then $D(n)=p^2q^2=(pq)^2=(n+1)^2$.

• If $n+1=pqr$, where $p,q,r$ are distinct primes, then

$$D(n) = p\cdot q\cdot r\cdot (pq)\cdot (pr)\cdot (qr)\cdot (pqr)=(pqr)^4=(n+1)^4.$$

• More generally, if $n+1=\prod_{k=1}^s p_i$, where all the $p_i$ are distinct primes, then there is a number $N(s)$ such that $D(n) = (n+1)^{N(s)}.$ And $$N(s) = 1 + {s-1 \choose 1} + {s-1\choose 2}+{s-1\choose 3}+\cdots +{s-1\choose s-1}=2^{s-1}.$$ Thus, if $n+1=\prod_{k=1}^s p_i$, where all the $p_i$ are distinct primes, then $$D(n)=(n+1)^{2^{s-1}}.$$

• If $n+1=ab$, with $a,b>1$ and $\gcd(a,b)=1$, then $D(a-1)D(b-1)$ is a divisor of $D(n)$, but $D(n)\neq D(a-1)D(b-1)$. Notice that, in this case, we also have that $D(a-1)D(b-1)ab$ is a divisor of $D(n)$, and $D(a-1)D(b-1)ab=D(n)$ if and only if $a$ and $b$ are primes.

• If $n+1=pq^2$, where $p$ and $q$ are distinct primes, then: $$D(n) = p\cdot q\cdot q^2\cdot pq \cdot pq^2 = p^3q^6 = (pq^2)^3 = (n+1)^3.$$

-
In the general case, where $n+1=\prod_{i=1}^sp_i^{e_i}$, I believe we get $$D(n)=(n+1)^{\frac{1}{2}\prod_{i=1}^s(e_i+1)}$$If all the $e_i$ are even, so that the product of the $(e_i+1)$ is odd, then $n+1$ is a perfect square so that $(n+1)^\frac{1}{2}$ is an integer. –  robjohn Aug 20 '11 at 13:55
I haven't checked, but it very well may be. One just has to buckle down and deal with the combinatorics. –  Álvaro Lozano-Robledo Aug 20 '11 at 14:03

I don't mean to hijack Álvaro Lozano-Robledo's answer, but I can't fit all of this into a comment. Suppose $$n+1=\prod_{i=1}^sp_i^{e_i}$$ Then each term in the product of the factors of $n+1$ looks like $$p_1^{k_1}\dots p_i^{k_i}\dots p_s^{k_s}$$ where $0\le k_i\le e_i$ for $1\le i\le s$. Concentrate on a particular $p_i$. For each $k_i$, $p_i^{k_i}$ appears $$r_i=\prod_{j=1,j\neq i}^s(e_j+1)$$ times as the other $k_j$ go through their possible values from $0$ to $e_j$. Summing $k_i$ for each choice from $0$ to $e_i$, we get $\frac{e_i(e_i+1)}{2}$. Multiplying this by $r_i$, we get the total exponent for $p_i$ to be $$\frac{e_i}{2}\prod_{j=1}^s(e_j+1)$$ Thus, we get that \begin{align} D(n)&=\prod_{i=1}^s p_i^{\frac{e_i}{2}\prod_{j=1}^s(e_j+1)}\\ &=(n+1)^{\frac{1}{2}\prod_{j=1}^s(e_j+1)} \end{align}

-
Very nice! I was hoping that someone would finish my train of thought. –  Álvaro Lozano-Robledo Aug 20 '11 at 15:12
By the way, my answer was meant to be pedagogical, in the sense that I was hoping the OP would see how one goes through the motions of trying to deduce a general formula... Your post concludes the lesson :) –  Álvaro Lozano-Robledo Aug 20 '11 at 15:37
Thanks, you guys. I will study this and try to learn from it. I really appreciate the work you put into this, both @Álvaro Lozano-Robledo and robjohn. –  Matt Groff Aug 21 '11 at 1:33