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