2
$\begingroup$

(This post is an offshoot of this MSE question.)

Let $\sigma(x)$ denote the sum of divisors of $x$. (https://oeis.org/A000203)

QUESTION

Is the asymptotic density of positive integers $n$ satisfying $\gcd(n, \sigma(n^2))=\gcd(n^2, \sigma(n^2))$ equal to zero?

I tried searching for examples and counterexamples to the equation $$\gcd(n, \sigma(n^2))=\gcd(n^2, \sigma(n^2))$$ via Sage Cell Server, it gave me this output for the following Pari-GP script:

for(x=1, 100, if(gcd(x,sigma(x^2))==gcd(x^2,sigma(x^2)),print(x)))

All positive integers from $1$ to $100$ (except for the integer $99$) satisfy $\gcd(n, \sigma(n^2))=\gcd(n^2, \sigma(n^2))$.

Generalizing the first (counter)example of $99$ is trivial.

If ${3^2}\cdot{11} \parallel n$, then $11 \parallel \gcd(n,\sigma(n^2))$ and $11^2 \parallel \gcd(n^2,\sigma(n^2))$. So the asymptotic density in question is less than $$1-\frac{2}{3^3}\cdot\frac{10}{11^2} = \frac{3247}{3267} \approx 0.993878.$$

Also, if $3 \parallel n$, then with probability $1$ there exist two distinct primes $y$ and $z$ congruent to $1$ modulo $3$ such that $y \parallel n$ and $z \parallel n$. In this case, we get $3 \parallel \gcd(n,\sigma(n^2))$ and $3^2 \parallel \gcd(n^2,\sigma(n^2))$. So the asymptotic density in question is less than $$1-\frac{2}{3^2} = \frac{7}{9} \approx 0.\overline{777}.$$

The real open problem is whether the asymptotic density is $0$.

$\endgroup$
2
$\begingroup$

I think the density does go to zero, but quite slowly. If $p \equiv 1 \bmod 6$ is prime then there are two solutions $0<r<s<p-1$ of $$x^2+x+1=0 \bmod p$$

If $p\parallel n$ then, with probability $1,$ there are two distinct primes $x $ and $ y,$ each congruent to $r \bmod p,$ with $x \parallel n$ and $y \parallel n.$ ( Either or both could be congruent to $s$ as well.)

Then $p \parallel \gcd(n,\sigma(n^2))$ while $p^2 \parallel \gcd(n^2,\sigma(n^2)).$ So the asymptotic density for this not to happen is $1-\frac{p-1}{p^2}<1-\frac{1}{p+2}$

If we can argue that the chance that none of these events happen is asymptotically $\prod(1-\frac{p-1}{p^2})$ over the primes congruent to $1 \bmod 6,$ then that asymptotic density is $0.$

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thank you for your answer, @AaronMeyerowitz. Assuming $$1 - \frac{p-1}{p^2} < 1 - \frac{1}{p-1}$$ is correct, then we obtain $$\frac{1}{p-1} < \frac{p-1}{p^2}$$ which implies that $$p^2 < (p-1)^2 = p^2 - 2p + 1$$ resulting in the contradiction $$p < \frac{1}{2}.$$ Hence, I am led to conclude that there must be a typo in your upper bound for $$1 - \frac{p-1}{p^2}.$$ $\endgroup$ – Arnie Bebita-Dris Aug 19 at 1:41
  • $\begingroup$ OK, I fixed it. Though I hadn't used it. The idea was, roughly $1-\frac{1}{p}$ $\endgroup$ – Aaron Meyerowitz Aug 19 at 2:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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