Search This Blog

16.4.20

When does $\gcd(m,\sigma(m^2))$ equal $\gcd(m^2,\sigma(m^2))$? What are the exceptions?

This post is taken verbatim from this MSE question.


(This question is related to this earlier one.)

Let $\sigma(x)$ be the sum of divisors of the positive integer $x$.  The greatest common divisor of the integers $a$ and $b$ is denoted by $\gcd(a,b)$.

Here are my questions:

When does $\gcd(m,\sigma(m^2))$ equal $\gcd(m^2,\sigma(m^2))$?  What are the exceptions?

I tried searching for examples and counterexamples via Sage Cell Server, it gave me these outputs for the following GP scripts:

    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(m,\sigma(m^2))=\gcd(m^2,\sigma(m^2))$.

    for(x=1, 1000, if(gcd(x,sigma(x^2))<>gcd(x^2,sigma(x^2)),print(x)))

The following integers in the range $1 \leq m \leq 1000$ DO NOT satisfy $\gcd(m,\sigma(m^2))=\gcd(m^2,\sigma(m^2))$:
$$99 = {3^2}\cdot{11}$$
$$154 = 2\cdot 7\cdot 11$$
$$198 = 2\cdot{3^2}\cdot{11}$$
$$273 = 3\cdot 7\cdot 13$$
$$322 = 2\cdot 7\cdot 23$$
$$396 = {2^2}\cdot{3^2}\cdot{11}$$
$$399 = 3\cdot 7\cdot 19$$
$$462 = 2\cdot 3\cdot 7\cdot 11$$
$$469 = 7\cdot 67$$
$$495 = {3^2}\cdot 5\cdot 11$$
$$518 = 2\cdot 7\cdot 37$$
$$546 = 2\cdot 3\cdot 7\cdot 13$$
$$553 = 7\cdot 79$$
$$620 = {2^2}\cdot 5\cdot 31$$
$$651 = 3\cdot 7\cdot 31$$
$$693 = {3^2}\cdot 7\cdot 11$$
$$741 = 3\cdot 13\cdot 19$$
$$742 = 2\cdot 7\cdot 53$$
$$770 = 2\cdot 5\cdot 7\cdot 11$$
$$777 = 3\cdot 7\cdot 37$$
$$792 = {2^3}\cdot{3^2}\cdot 11$$
$$798 = 2\cdot 3\cdot 7\cdot 19$$
$$903 = 3\cdot 7\cdot 43$$
$$938 = 2\cdot 7\cdot 67$$
$$966 = 2\cdot 3\cdot 7\cdot 23$$
$$990 = 2\cdot{3^2}\cdot 5\cdot 11$$

MY ATTEMPT

I know that primes $m_1 := p$ and prime powers $m_2 := q^k$ satisfy the equation, since then we have
$$\gcd(m_1, \sigma({m_1}^2)) = \gcd(p, \sigma(p^2)) = 1 = \gcd(p^2, \sigma(p^2)) = \gcd({m_1}^2, \sigma({m_1}^2)),$$
and
$$\gcd(m_2, \sigma({m_2}^2)) = \gcd(q^k, \sigma(q^{2k})) = 1 = \gcd(q^{2k}, \sigma(q^{2k})) = \gcd({m_2}^2, \sigma({m_2}^2)).$$

This shows that there are infinitely many solutions to the equation
$$\gcd(m, \sigma(m^2)) = \gcd(m^2, \sigma(m^2)).$$

Follow-Up Questions

What can be said about solutions to $\gcd(m, \sigma(m^2)) = \gcd(m^2, \sigma(m^2))$ for which the number of distinct prime factors $\omega(m)$ satisfies

(a) $\omega(m)=2?$

(b) $\omega(m)=3?$

15.4.20

If $q^k n^2$ is an odd perfect number with special prime $q$, then $\gcd(\sigma(q^k),\sigma(n^2))=i(q)=\gcd(n^2, \sigma(n^2))$ (subject to a certain condition).

Let $N = q^k n^2$ be an odd perfect number with special prime $q$.

From this paper in NNTDM, we have the equation
$$i(q) := \frac{\sigma(n^2)}{q^k}=\frac{2n^2}{\sigma(q^k)}=\frac{D(n^2)}{\sigma(q^{k-1})}=\gcd\left(n^2,\sigma(n^2)\right).$$

In particular, we know that the index $i(q)$ is an integer greater than $5$ by a result of Dris and Luca.


Here is a conditional proof (copied from MathOverflow) that
$$\gcd(\sigma(q^k),\sigma(n^2)) = i(q) = \gcd(n^2, \sigma(n^2)).$$

First, since we have 
$$\sigma(q^k)\sigma(n^2) = \sigma({q^k}{n^2}) = \sigma(N) = 2N = 2{q^k}{n^2}$$
we obtain
$$\sigma(q^k) = \frac{2 q^k n^2}{\sigma(n^2)} = \frac{2n^2}{\sigma(n^2)/q^k} = \frac{2n^2}{i(q)}$$
and
$$\sigma(n^2) = \frac{2 q^k n^2}{\sigma(q^k)} = {q^k}\cdot\bigg(\frac{2n^2}{\sigma(q^k)}\bigg) = {q^k}{i(q)},$$
so that we get
$$\gcd\left(\sigma(q^k),\sigma(n^2)\right) = \gcd\bigg(\frac{2n^2}{i(q)}, {q^k}{i(q)}\bigg).$$

Now, since $\gcd(q, n) = \gcd(q^k, 2n^2) =  1$ and $i(q)$ is odd, we get
$$\gcd\bigg(\frac{2n^2}{i(q)}, {q^k}{i(q)}\bigg) = \gcd\bigg(\frac{n^2}{i(q)}, i(q)\bigg).$$

Hence, we conclude that $G:=\gcd(\sigma(q^k),\sigma(n^2))=\gcd\bigg({n^2}/{i(q)}, i(q)\bigg)$.

This is equivalent to
$$G = \frac{1}{i(q)}\cdot\gcd\bigg(n^2, (i(q))^2\bigg) = \frac{1}{i(q)}\cdot\bigg(\gcd(n, i(q))\bigg)^2.$$

But we also have
$$\gcd(n, i(q)) = \gcd\bigg(n, \gcd(n^2, \sigma(n^2))\bigg)$$
$$= \gcd\bigg(\sigma(n^2), \gcd(n, n^2)\bigg) = \gcd(n, \sigma(n^2)).$$

Consequently, we obtain
$$G = \frac{1}{i(q)}\cdot\bigg(\gcd(n, \sigma(n^2))\bigg)^2 = \frac{\bigg(\gcd(n, \sigma(n^2))\bigg)^2}{\gcd(n^2, \sigma(n^2))}.$$

In particular, we get
$$\gcd(\sigma(q^k), \sigma(n^2)) = i(q) = \gcd(n^2, \sigma(n^2)),$$
if and only if $\gcd(n^2, \sigma(n^2)) = \gcd(n, \sigma(n^2))$.

31.3.20

K. A. P. Dagal's "A New Operator for Egyptian Fractions"

My friend, Keneth Adrian P. Dagal, has a new preprint out there (uploaded to the math.HO subject area in arXiv), titled "A New Operator for Egyptian Fractions".

Here is the abstract:

This paper introduces a new equation for rewriting two unit fractions to another two unit fractions. This equation is useful for optimizing the elements of an Egyptian Fraction. Parity of the elements of the Egyptian Fractions are also considered. And lastly, the statement that all rational numbers can be represented as Egyptian Fraction is re-established.

25.3.20

Summing Odd Fractions to One, and Odd Perfect Numbers

(This blog post is lifted verbatim from this MSE question, and the answers and a comment contained therein.)

The title says it all.

Question

What exactly is the relationship between Egyptian/unit fractions with odd denominators, and odd perfect numbers?

Motivation

In a comment underneath the question Summing Odd Fractions to One:

From the list $\frac{1}{3},\frac{1}{5},\frac{1}{7},\frac{1}{9},\frac{1}{11}$..... is it possible to choose a limited number of terms that sum to one?
This can be done with even fractions: $\frac{1}{2},\frac{1}{4},\frac{1}{8},\frac{1}{12},\frac{1}{24}$

it is stated that:

This would be true if an odd perfect number existed :) MSE user idok

Is this claim true/valid?


Such a representation of a fraction as the sum of fractions with numerator 1 and different denominators is called Egyptian fraction, because that was the way fractions were written in ancient Egypt. It's clear that for 1, we must have an odd number of summands, because otherwise the numerator of the sum would be even and the denominator odd. As it turns out, the minimal number is 9, and there are the following 5 solutions:
$1=\frac{1}{3}+\frac{1}{5}+\frac{1}{7}+\frac{1}{9}+\frac{1}{11}+\frac{1}{15}+\frac{1}{35}+\frac{1}{45}+\frac{1}{231}$

$1=\frac{1}{3}+\frac{1}{5}+\frac{1}{7}+\frac{1}{9}+\frac{1}{11}+\frac{1}{15}+\frac{1}{21}+\frac{1}{231}+\frac{1}{315}$

$1=\frac{1}{3}+\frac{1}{5}+\frac{1}{7}+\frac{1}{9}+\frac{1}{11}+\frac{1}{15}+\frac{1}{33}+\frac{1}{45}+\frac{1}{385}$

$1=\frac{1}{3}+\frac{1}{5}+\frac{1}{7}+\frac{1}{9}+\frac{1}{11}+\frac{1}{15}+\frac{1}{21}+\frac{1}{165}+\frac{1}{693}$

$1=\frac{1}{3}+\frac{1}{5}+\frac{1}{7}+\frac{1}{9}+\frac{1}{11}+\frac{1}{15}+\frac{1}{21}+\frac{1}{135}+\frac{1}{10395}$
There are also solutions of length 11, 13, 15,..., and it can be shown that every odd length $\ge 9$ is possible. This information (and further references) can be found in this article.

Does this answer make the existence of an odd perfect number more likely?

Background

The topic of odd perfect numbers likely needs no introduction, but I include this section here for completion.

A positive integer $n$ is said to be perfect if $\sigma(n)=2n$, where $\sigma(x)$ is the sum of divisors of $x \in \mathbb{N}$.  If $N$ is odd and $\sigma(N)=2N$, then $N$ is called an odd perfect number.  It is currently unknown whether there is an odd perfect number, despite extensive computer searches.

Euler proved that an odd perfect number, if one exists, must have the form $N=p^k m^2$ where $p$ is the special/Euler prime satisfying $p \equiv k \equiv 1 \pmod 4$ and $\gcd(p,m)=1$.

Comment underneath the question: Reference: Sellers, J. A., Egyptian Fractions and Perfect Numbers, The Mathematics Teacher, 87, no. 1 (January 1994), 60

Accepted Answer (by MSE user Servaes)

The claim is true because $1$ is the sum of finitely many fractions with odd denominator and unit numerator. More generally, for any statement $P$ the implication $P \Longrightarrow Q$ is true if $Q$ is true. This says nothing about the truth value of $P$, however. In this particular case, this doesn't make the existence of odd perfect numbers any more or less likely. In this sense the quoted comment is a bit misleading.

Rebuttal (by MSE user Thomas Bloom)

I don't think the answer by Servaes is right, because there is a direct (non-trivial) link. Suppose $n$ is an odd perfect number. Then

$$ \sum_{d\mid n} d = 2n.$$

Divide both sides by $n$ and we get

$$ \sum_{d\mid n} \frac{1}{d} = 2.$$

Subtracting $1$ from both sides we have written $1$ as the sum of $1/d$ where $d$ are all odd numbers (since all are divisors of $n$, which is odd).

Further Research:

The following MSE questions are also tangentially related to this blog post:

On the decomposition of $1$ as the sum of Egyptian fractions with odd denominators

and

On the decomposition of $1$ as the sum of Egyptian fractions with odd denominators - Part II

18.3.20

On some inequalities relating the special/Euler prime and non-Euler part of odd perfect numbers

(Note:  The contents of this blog post were taken verbatim from this MSE question, dated January 9, 2019.)


Let $N$ be an odd (positive) integer.  If $\sigma(N)=2N$ where $\sigma(N)$ is the sum of the divisors of $N$, then $N$ is called an odd perfect number.  Let $I(N)=\sigma(N)/N$ denote the abundancy index of $N$.  Likewise, denote the deficiency of $x \in \mathbb{N}$ by $D(x)=2x-\sigma(x)$, and the sum of the aliquot divisors of $x$ by $s(x)=\sigma(x)-x$.

Euler showed that an odd perfect number, if one exists, must have the so-called Eulerian form $N = q^k n^2$, where $q$ is the special/Euler prime satisfying $q \equiv k \equiv 1 \pmod 4$ and $\gcd(q,n)=1$.

The question on the existence of an odd perfect number is one of the long-standing open problems of number theory.

Since $\gcd(q,n)=1$ and the abundancy index function $I$ is multiplicative, we have
$$\sigma(N)=2N \iff I(N)=2=I(q^k)I(n^2)$$
$$\iff \frac{\sigma(q^k)}{q^k} = I(q^k) = \frac{2}{I(n^2)} = \frac{2n^2}{\sigma(n^2)}.$$

Using the formula
$$\frac{A}{B}=\frac{C}{D}=\frac{C-A}{D-B}$$
and the substitutions $A=\sigma(q^k)$, $B=q^k$, $C=2n^2$, and $D=\sigma(n^2)$, and noting that $C-A > 0$ and $D-B > 0$ (see this paper by Dris (2012) for more information), we obtain
$$\frac{\sigma(q^k)}{q^k} = I(q^k) = \frac{2}{I(n^2)} = \frac{2n^2}{\sigma(n^2)} = \frac{2n^2 - \sigma(q^k)}{\sigma(n^2) - q^k}.$$

Using the known bounds  
$$\frac{q+1}{q} \leq I(q^k) < \frac{q}{q-1}$$
we get the system of inequalities
$$(q+1)(\sigma(n^2) - q^k) \leq 2qn^2 - q\sigma(q^k)$$
and
$$(q-1)(2n^2 - \sigma(q^k)) < q(\sigma(n^2) - q^k)$$
from which we get
$$q\sigma(q^{k-2})= q(\sigma(q^{k-1}) - q^{k-1}) = q(s(q^k) - q^{k-1}) = qs(q^k) - q^k \leq qD(n^2) - \sigma(n^2)$$
and
$$qD(n^2) - 2n^2 < qs(q^k) - \sigma(q^k) = q\sigma(q^{k-1}) - \sigma(q^k) = -1,$$
of which the last inequality implies that
$$q < \frac{2n^2 - 1}{D(n^2)} = \frac{2n^2 - 1}{2n^2 - \sigma(n^2)}.$$

The two resulting inequalities may be summarized as follows:

If $N=q^k n^2$ is an odd perfect number given in Eulerian form, then
$$q\sigma(q^{k-2}) + \sigma(n^2) \leq qD(n^2) < 2n^2 - 1.$$

Consequently, we have
$$q\sigma(q^{k-2}) + \sigma(n^2) < 2n^2 - 1 \Longrightarrow D(n^2) > q\sigma(q^{k-2}) + 1.$$

However, this last inequality appears to be trivial, as it is known that
$$\frac{\sigma(n^2)}{q^k}=\frac{2n^2}{\sigma(q^k)}=\gcd(n^2,\sigma(n^2))=\frac{D(n^2)}{s(q^k)}=\frac{2s(n^2)}{D(q^k)}$$
so that, if we are willing to assume the Descartes-Frenicle-Sorli Conjecture that $k=1$, and knowing that this conjecture implies $\sigma(q^k) < n$ (see this paper by Dris (2017) for more information), then we obtain
$$\frac{\sigma(n^2)}{q^k}=\gcd(n^2,\sigma(n^2))=\frac{D(n^2)}{s(q^k)}=\frac{2s(n^2)}{D(q^k)}=\frac{2n^2}{\sigma(q^k)}>2n>\sigma(n).$$

(Please see OEIS sequence A322154 for more information.)

Here is my question:

Is it possible to tweak the argument presented in this MSE post in order to come up with a lower bound better than $D(n^2) > 2n$?

I am guessing our best shot would have to emanate from the inequality
$$\sigma(q^{k-2}) + \frac{\sigma(n^2)}{q} \leq D(n^2)$$
where equality holds if and only if $k=1$ (whence $\sigma(q^{k-2})=0$ since it would be an empty sum).

So suppose that $k>1$.  It follows from our method that
$$\sigma(q^{k-2}) + \frac{\sigma(n^2)}{q} < D(n^2) = s(q^k)\frac{\sigma(n^2)}{q^k} = \sigma(q^{k-1})\frac{\sigma(n^2)}{q^k}$$
from which we obtain
$$\frac{\sigma(q^{k-2})}{\sigma(q^{k-1})} + \frac{\sigma(n^2)}{q\sigma(q^{k-1})} < \frac{\sigma(n^2)}{q^k}$$
which is trivial as
$$\sigma(q^{k-2}) < \sigma(q^{k-1})$$
while
$$q^k < q\sigma(q^{k-1}) = q(1 + \ldots + q^{k-1}) = q + \ldots + q^k.$$

20.1.20

Evidence for the Descartes-Frenicle-Sorli Conjecture on odd perfect numbers

Let $N = p^k m^2$ be an odd perfect number with special / Euler prime $p$ satisfying $p \equiv k \equiv 1 \pmod 4$ and $\gcd(p, m)=1$.

First, we state the following conjectures, which are currently open (as of January 2020):

Descartes-Frenicle-Sorli Conjecture
If $N = p^k m^2$ is an odd perfect number with special / Euler prime $p$, then $k = 1$ always holds.

Dris Conjecture
If $N = p^k m^2$ is an odd perfect number with special / Euler prime $p$, then $p^k < m$ always holds.

Remark 1:  Note that Dris Conjecture implies that $p < m$.

Motivation for the Present Blog Post

Since $m$ is odd, $m^2 \equiv 1 \pmod 4$.  Additionally, $p \equiv k \equiv 1 \pmod 4$ imply that $p^k \equiv 1 \pmod 4$.  Together, the congruences for $m^2$ and $p^k$ imply that $m^2 - p^k \equiv 0 \pmod 4$.  Additionally, note that it is known that
$$p^k < \frac{2}{3}{m^2},$$
so that we know a priori that
$$m^2 - p^k > \frac{p^k}{2}.$$
In particular, we are sure that
$$m^2 - p^k > 0.$$

Since $m^2 - p^k > 0$ and $m^2 - p^k \equiv 0 \pmod 4$, we are led to the considerations in the following MSE question:

We reproduce here the accepted answer by MSE user mathlove:

This is a partial answer. 

Your idea works for $z=2^{2n}$.

Claim: For $z=2^{2n}$, if $2^{n+2}+1$ is prime, then $(m,p,k)=(2^{n+1}+1,2^{n+2}+1,1)$. If $2^{n+2}+1$ is not prime, then there is no solution.

Proof:

For $z=2^{2n}$, we have

$$m^2 - p^k = 2^{2n+2}\iff p^k=(m-2^{n+1})(m+2^{n+1})$$
So, there is a non-negative integer $a$ such that
$$m+2^{n+1}=p^{k-a},m-2^{n+1}=p^a \Longrightarrow 2^{n+2}=p^a(p^{k-2a}-1)$$
Since $\gcd(2,p)=1$, we get $a=0$ to have
$$ p^{k}-2^{n+2}=1$$

If $2^{n+2}+1$ is prime, then $k=1$.

If $2^{n+2}+1$ is not prime, then $k\ge 2$. By Catalan's conjecture (or Mih─âilescu's theorem), there is no solution.

Remark 2:  Note that when $z = 2^{2n}$, there is a solution only if the Descartes-Frenicle-Sorli Conjecture that $k=1$ on odd perfect numbers holds.  But even then, note that
$$m = 2^{n+1}+1 < 2^{n+2}+1 = p$$
which would contradict the Dris conjecture.

Final Notes:

From the following MSE question:
it appears that MSE user FredH has already been able to come up with an unconditional proof for the problem as stated in the title.

We reproduce FredH's proof here:

Here's a way to finish the proof without appealing to any conjecture.

If $q^k n^2$ is a perfect number with $\gcd(q,n)=1$, we have
$$\sigma(q^k) \sigma(n^2) = 2 q^k n^2.$$
We know that $\sigma(q^k) = (q^{k+1}-1)/(q-1)$ and you've shown that $n = (q^k + 1)/2$,  so we can conclude that
$$2(q^{k+1}-1) \sigma(n^2) = (q-1) q^k (q^k + 1)^2.          (*)$$
Consider the GCD of $q^{k+1}-1$ with the right-hand side:
$$\gcd(q^{k+1}-1, (q-1) q^k (q^k + 1)^2) \le (q-1)\gcd(q^{k+1}-1,q^k+1)^2,$$
since $q^k$ is coprime to $q^{k+1} - 1$.

Noticing that $q^{k+1} - 1$ = $q(q^k + 1) - (q + 1)$, we find $\gcd(q^{k+1}-1,q^k+1) = \gcd(q+1,q^k+1)$, which is $q+1$ because $k$ is odd.

Thus
$$\gcd(q^{k+1}-1, (q-1) q^k (q^k + 1)^2) \le (q-1)(q+1)^2.$$
Since $k\equiv 1 \pmod 4$ and you have shown $k \gt 1$, we have $k \ge 5$.  If $(*)$ holds, the left-hand side of the inequality must be $q^{k+1}-1$, which is then greater than $q^5$.  But the right-hand side is less than $q^4$, so this is impossible.

31.10.19

Expressing $\gcd(m^2, \sigma(m^2))$ as a linear combination - Part II

Let $N = p^k m^2$ be an odd perfect number with special / Euler prime $p$.

Continuing from the previous blog post titled



it is perhaps worthwhile and instructive to consider what would happen if one assumes that the Descartes-Frenicle-Sorli Conjecture that $k=1$ hold.

From the final equation in that blog post, we have
$$\gcd(m^2, \sigma(m^2))=\frac{\sigma(m^2)}{p^k}=\frac{2m^2}{\sigma(p^k)}$$
$$=\frac{D(m^2)}{s(p^k)}=\frac{2s(m^2)}{D(p^k)}=p\sigma(m^2) - 2(p-1){m^2},$$
where $\sigma(x)$ is the sum of divisors of $x$, $D(x)=2x-\sigma(x)$ is the deficiency of $x$, and $s(x)=\sigma(x)-x$ is the sum of the proper/aliquot divisors of $x$.

Now, assume that $k=1$.

Dividing both sides of
$$\gcd(m^2, \sigma(m^2))=p\sigma(m^2) - 2(p-1){m^2}$$
by $pm^2$, we get
$$\frac{D(m^2)}{N}=I(m^2) - 2\cdot\bigg(\frac{p-1}{p}\bigg),$$
where $I(x)=\sigma(x)/x$ is the abundancy index of $x$.

Since $k=1$, we get
$$I(p^k)=I(p)=\frac{p+1}{p}$$
from which we obtain
$$I(m^2)=\frac{2}{I(p^k)}=\frac{2p}{p+1}.$$
Finally, we derive
$$\frac{D(m^2)}{N}=\frac{2p}{p+1} - 2\cdot\bigg(\frac{p-1}{p}\bigg)=\frac{2}{p(p+1)},$$
which gives some insight as to where the expression
$$N = \frac{p(p+1)}{2}\cdot{D(m^2)}$$
comes from, when the Descartes-Frenicle-Sorli Conjecture that $k=1$ holds.