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
    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$. :-(2011-08-20
  • 0
    For $n$=a prime $p$-1, the product appears to be 0.2011-08-20
  • 3
    Wait, are you not simply looking at the product of the divisors of n+1, the integer n+1 excepted...2011-08-20
  • 0
    I find your notation a bit confusing. You appear to follow the syntax of a binary mod, but yet you talk about congruences. $5\equiv 1 \pmod{2}$ is a congruence, $(5\bmod2)=1$ is the corresponding remainder operation. At least that's how I currently understand it :-)2011-08-20
  • 0
    @Didier Piau: I think I realized that they're the same thing - but I was trying to create a list of numbers for Chinese Remainder Theorem. Now I guess I won't have luck, because they don't appear to have a large enough product, which is what I was hoping for.2011-08-20
  • 1
    But Didier's point is the key. Try $n=29$. Your list then contains 15,10,6,5,3,2.2011-08-20
  • 0
    @Jyrki Lahtonen: I tried to describe the remainder operation. Sorry for being naive; I forgot to notice the difference. Btw, I hope Bricks is going well for you!2011-08-20
  • 0
    That's right! It really looks like the list of divisors! My search might not be in vain! So I wonder if there's a way to find a number that maximizes divisors...perhaps another question...2011-08-20
  • 0
    NP. I often get cranky with binary mod, but I try to learn. My Bricks is so-so, but my son is dominating the scene. Returning to the problem: Take a lot of small primes, and let $n$ be their product minus one. You get a lot of $m$:s, then!2011-08-20
  • 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$.2011-08-20
  • 0
    Ok, so for $n$=29 the product of the $m$'s is 29000. For $n$=59, the product is 777,600,000. I'm guessing the maximum product is squared as $n$ is doubled.2011-08-20
  • 0
    Matt: For n=29 the product is certainly not 29,000. Please read again @Jyrki's explanation (or mine) or start with the observation that n=29 is not m-1 mod m for m=29 hence 29 is NOT in your list.2011-08-20
  • 0
    @Gerry: you are right, I do not know why I excluded n+1 from the list.2011-08-20
  • 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.$$

  • 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.2011-08-20
  • 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
    Very nice! I was hoping that someone would finish my train of thought.2011-08-20
  • 0
    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 :)2011-08-20
  • 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