3
$\begingroup$

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?

  • 0
    There's definitely a "curve" to the values. I get $n$=11, product = 1,728 $n$ = 29, product=870,000 $n$=59 product=46,656,000,000...2011-08-20

2 Answers 2

3

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.$

  • 0
    I haven't checked, but it very well may be. One just has to buckle down and deal with the combinatorics.2011-08-20
3

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} $

  • 0
    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.2011-08-21