Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
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
3  
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
1  
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
2  
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

2 Answers 2

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

share|improve this answer
1  
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} $$

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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