Euler’s construction problems

L. Euler³⁶⁴ obtained, in addition to two special pairs, 62 pairs [including two false pairs] of amicable numbers of the type $am,an$, in which the common factor $a$ is relatively prime to both $m$ and $n$. He wrote $\int m$ for the sum of all the divisors of $m$. The conditions are therefore

$$\int m=\int n,\qquad\int a\cdot\int m=a(m+n).$$

If $m$ and $n$ are both primes, then $m=n$ and we have a repeated perfect number. Euler treated five problems.

(1) Euler's problem 1 is to find amicable numbers $apq,ar$, where $p,q,r$, are distinct primes not dividing the given number $a$. From the first condition we have $r=xy-1$, where $x=p+1$, $y=q+1$. From the second,

$$xy\int a=a(2xy-x-y).$$

Let $a/(2a-\int a)$ equal $b/c$, a fraction in its lowest terms. Then

$$y=bx/(cx-b),\qquad(cx-b)(cy-b)=b^2.$$

Thus $x$ and $y$ are to be found by expressing $b^2$ as a product of two factors, increasing each by $b$, and dividing the results by $c$.

(2) Euler's problem 2 is to find amicable numbers $apq,ars$, where $p,q,r,s$ are distinct primes not dividing the given number $a$. Since $\int p\cdot\int q=\int r\cdot\int s$, we may set

$$p=\alpha x-1,\quad q=\beta y-1,\quad r=\beta x-1,\quad s=\alpha y-1.$$

We set $\int a:a=2b-c:b$, where $b$ and $c$ are relatively prime. The second condition $\int a\cdot\int pq=a(pq+rs)$ gives

$$c\alpha\beta xy=b(\alpha+\beta)(x+y)-2b.$$

Multiply it by $c\alpha\beta$. Then

$$[c\alpha\beta x-b(\alpha+\beta)][c\alpha\beta y-b(\alpha+\beta)]=b^2(\alpha+\beta)^2-2bc\alpha\beta.$$

Given $\alpha,\beta,a$ and hence $b,c$, we are to express the second member as a product of two factors and then find $x,y$.

(3) Problem 3 is derived from problem 2 by replacing $s$ by a number $f$ not necessarily prime. Let $h$ be the greatest common divisor of $\int f=hg$ and $p+1=hx$. Then $r+1=xy$, $q+1=gy$. Also

$$ghxy\int a=\int(afr)=a(pq+fr)=a\{(hx-1)(gy-1)+f(xy-1)\}.$$

Multiply by $b/a$ and replace $b\int a$ by $2ab-ac$ [see case (1)]. Thus

$$exy-bhx-bgy=b(f-1),\qquad e=bf-bgh+cgh.$$

Thus $L=b^2gh+be(f-1)$ is to be expressed as the product $PQ$ of two factors and they are to be equated to $ex-bg$, $ey-bh$. The case $a=2$ is unfruitful.

(4) Problem 4 relates to amicable numbers $agpq,ahr$, where $p,q,r$ are primes. Eventually he took also $g$ and $h$ as primes. We may then set $g+1=km$, $h+1=kn$. For $m=1$, $n=3$, $a=4$ or 8, no amicables are found. For $m=3$, $n=1$, the cases $a=10$, $k=8$ and $a=3^3\cdot5$, $k=8$, yield (38), (55).

(5) Euler's final problem 5 is of a new type. He discussed amicable numbers $zap,zbq$, where $a$ and $b$ are given numbers, $p$ and $q$ are unknown primes, while $z$ is unknown but relatively prime to $a,b,p,q$. Set $\int a:\int b=m:n$, where $m$ and $n$ are relatively prime. Since $(p+1)\int a=(q+1)\int b$, we may set $p+1=nx$, $q+1=mx$. The usual second condition gives

$$nx\int a\cdot\int z=za(nx-1)+zb(mx-1),\qquad\frac{z}{\int z}=\frac{nx\int a}{(na+mb)x-a-b}.$$

Let the latter fraction in its lowest terms be $r/s$. Then $z=kr$, $\int z=ks$. Since $\int(kr)\geqq k\int r$, we have $s\geqq\int r$. Hence we have the useful theorem:

if $z:\int z=r':s'$, $s'<\int r'$, then $r'$ and $s'$ have a common factor $>1$.

Paganini³⁷², at age 16, announced the amicable numbers $1184=2^5\cdot37$, $1210=2\cdot5\cdot11^2$, not in the list by Euler³⁶⁴, but gave no indication of the method of discovery.

L. Euler³⁶⁴ obtained, in addition to two special pairs, 62 pairs [including two false pairs] of amicable numbers of the type $am,an$, in which the common factor $a$ is relatively prime to both $m$ and $n$. Write $\sigma(m)$ for the sum of all positive divisors of $m$ (Euler’s $\int m$). The conditions are therefore

$$\sigma(m)=\sigma(n),\qquad\sigma(a)\cdot\sigma(m)=a(m+n).$$

If $m$ and $n$ are both primes, then $m=n$ and we have a repeated perfect number. Euler treated five problems.

(1) Euler's problem 1 is to find amicable numbers $apq,ar$, where $p,q,r$, are distinct primes not dividing the given number $a$. From the first condition we have $r=xy-1$, where $x=p+1$, $y=q+1$. From the second,

$$xy\sigma(a)=a(2xy-x-y).$$

Let $a/(2a-\sigma(a))$ equal $b/c$, a fraction in its lowest terms. Then

$$y=bx/(cx-b),\qquad(cx-b)(cy-b)=b^2.$$

Thus $x$ and $y$ are to be found by expressing $b^2$ as a product of two factors, increasing each by $b$, and dividing the results by $c$.

(2) Euler's problem 2 is to find amicable numbers $apq,ars$, where $p,q,r,s$ are distinct primes not dividing the given number $a$. Since $\sigma(p)\cdot\sigma(q)=\sigma(r)\cdot\sigma(s)$, we may set

$$p=\alpha x-1,\quad q=\beta y-1,\quad r=\beta x-1,\quad s=\alpha y-1.$$

We set $\sigma(a):a=2b-c:b$, where $b$ and $c$ are relatively prime. The second condition $\sigma(a)\cdot\sigma(pq)=a(pq+rs)$ gives

$$c\alpha\beta xy=b(\alpha+\beta)(x+y)-2b.$$

Multiply it by $c\alpha\beta$. Then

$$[c\alpha\beta x-b(\alpha+\beta)][c\alpha\beta y-b(\alpha+\beta)]=b^2(\alpha+\beta)^2-2bc\alpha\beta.$$

Given $\alpha,\beta,a$ and hence $b,c$, we are to express the second member as a product of two factors and then find $x,y$.

(3) Problem 3 is derived from problem 2 by replacing $s$ by a number $f$ not necessarily prime. Let $h$ be the greatest common divisor of $\sigma(f)=hg$ and $p+1=hx$. Then $r+1=xy$, $q+1=gy$. Also

$$ghxy\sigma(a)=\sigma(afr)=a(pq+fr)=a\{(hx-1)(gy-1)+f(xy-1)\}.$$

Multiply by $b/a$ and replace $b\sigma(a)$ by $2ab-ac$ [see case (1)]. Thus

$$exy-bhx-bgy=b(f-1),\qquad e=bf-bgh+cgh.$$

Thus $L=b^2gh+be(f-1)$ is to be expressed as the product $PQ$ of two factors and they are to be equated to $ex-bg$, $ey-bh$. The case $a=2$ is unfruitful.

(4) Problem 4 relates to amicable numbers $agpq,ahr$, where $p,q,r$ are primes. Eventually he took also $g$ and $h$ as primes. We may then set $g+1=km$, $h+1=kn$. For $m=1$, $n=3$, $a=4$ or 8, no amicables are found. For $m=3$, $n=1$, the cases $a=10$, $k=8$ and $a=3^3\cdot5$, $k=8$, yield (38), (55).

(5) Euler's final problem 5 is of a new type. He discussed amicable numbers $zap,zbq$, where $a$ and $b$ are given numbers, $p$ and $q$ are unknown primes, while $z$ is unknown but relatively prime to $a,b,p,q$. Set $\sigma(a):\sigma(b)=m:n$, where $m$ and $n$ are relatively prime. Since $(p+1)\sigma(a)=(q+1)\sigma(b)$, we may set $p+1=nx$, $q+1=mx$. The usual second condition gives

$$nx\sigma(a)\cdot\sigma(z)=za(nx-1)+zb(mx-1),\qquad\frac{z}{\sigma(z)}=\frac{nx\sigma(a)}{(na+mb)x-a-b}.$$

Let the latter fraction in its lowest terms be $r/s$. Then $z=kr$, $\sigma(z)=ks$. Since $\sigma(kr)\geqq k\sigma(r)$, we have $s\geqq\sigma(r)$. Hence we have the useful theorem:

if $z:\sigma(z)=r':s'$, $s'<\sigma(r')$, then $r'$ and $s'$ have a common factor $>1$.

Paganini³⁷², at age 16, announced the amicable numbers $1184=2^5\cdot37$, $1210=2\cdot5\cdot11^2$, not in the list by Euler³⁶⁴, but gave no indication of the method of discovery.

Separate the common factor

Let $a,m,n$ be positive integers with $\gcd(a,mn)=1$ and $m\ne n$. Multiplicativity gives the equivalence

$$am,an\text{ amicable}\quad\Longleftrightarrow\quad\sigma(m)=\sigma(n),\qquad A(a)=\frac{m+n}{\sigma(m)}.$$

The first condition matches the residual divisor sums. The second sets the required abundance of the common factor. The factor $a$ need not be the greatest common divisor of the two numbers, but its coprimality with both residual factors is essential. If $m,n$ are both prime, the first equation forces $m=n$ and cannot give a distinct pair.

Euler's five problems prescribe different shapes for $m,n$, or leave the common factor unknown. Their central operation is completion of a product:

$$Kxy-Lx-My=R\quad\Longrightarrow\quad(Kx-M)(Ky-L)=LM+KR.$$

For fixed coefficients and nonzero $K$, the reverse implication also holds by expansion. A nonzero right side has finitely many integer factor pairs. Recovering integer parameters is only the first step: positivity, primality, distinctness and coprimality still have to be tested. If $K=0$, retain the linear equation; if the right side is zero, a finite list of nonzero divisor pairs no longer describes the problem.

Problem 1: two primes against one

Fix $a$ and seek $apq,ar$, with distinct primes $p,q,r$ not dividing $a$. Set $x=p+1$, $y=q+1$. Equality of divisor sums gives $r=xy-1$. The total-sum condition becomes

$$\sigma(a)xy=a(2xy-x-y),$$ $$Dxy=a(x+y),\qquad D=2a-\sigma(a).$$

Since $x,y>0$, necessarily $D>0$: the common factor must be deficient. Reduce $a/D=b/c$ with positive coprime integers $b,c$. Then

$$(cx-b)(cy-b)=b^2.$$

Moreover $cx>b$ and $cy>b$, by $cxy=b(x+y)$. Therefore it suffices to enumerate positive factor pairs $uv=b^2$, recover

$$x=\frac{u+b}c,\qquad y=\frac{v+b}c,$$ $$p=x-1,\qquad q=y-1,\qquad r=xy-1,$$

and retain precisely the integer outputs satisfying the prime and coprimality conditions. Every pair of this prescribed shape occurs: the equations were reversible and every positive factor pair is considered. This is completeness for the fixed $a$ and this shape, not for all amicable numbers.

For $a=4$, $D=1$, $b=4$, $c=1$. The unordered factor pairs of 16 are $(1,16),(2,8),(4,4)$. They give $(p,q,r)=(4,19,99),(5,11,71),(7,7,63)$. Only the middle row passes, producing $220,284$. The other rows explain why factorization alone is insufficient.

Problem 2: two primes against two

Seek $apq,ars$ with four distinct primes outside $a$. To satisfy $(p+1)(q+1)=(r+1)(s+1)$, use

$$p=\alpha x-1,\quad q=\beta y-1,\quad r=\beta x-1,\quad s=\alpha y-1.$$

This is not a guess without coverage: take $x=\gcd(p+1,r+1)$, write $p+1=\alpha x$, $r+1=\beta x$, and cancel the coprime $\alpha,\beta$ to obtain $q+1=\beta y$, $s+1=\alpha y$. Allowing noncoprime $\alpha,\beta$ can repeat parametrizations but does not invalidate an accepted pair.

Write $A(a)=2-c/b$ in lowest terms. For a valid pair, $c>0$: the equal residual divisor sum exceeds each residual number, so their sum divided by that divisor sum is less than 2. Substitution gives

$$c\alpha\beta xy=b(\alpha+\beta)(x+y)-2b.$$

Completing the product yields precisely Euler's factorization,

$$[c\alpha\beta x-b(\alpha+\beta)][c\alpha\beta y-b(\alpha+\beta)] =b^2(\alpha+\beta)^2-2bc\alpha\beta.$$

For fixed $a,\alpha,\beta$, enumerate integer factor pairs of the right side and test the recovered primes. These fixed-parameter searches do not bound all possible $a,\alpha,\beta$. Euler already makes this algebraic reduction; the gain here is identifying the reversible substitution and the limits of a finite search.

Problem 3: allow a composite residual factor

Now seek $apq,afr$, with $p,q,r$ prime and $f$ a given positive integer. We explicitly require

$$\gcd(a,pqfr)=1,\quad\gcd(f,r)=1,\quad p\ne q.$$

The source carries factor-separation assumptions implicitly from its preceding problems. They are written here because otherwise $\sigma(fr)=\sigma(f)(r+1)$ need not hold. The final numbers must also be distinct.

Let $h=\gcd(\sigma(f),p+1)$, so $\sigma(f)=hg$, $p+1=hx$, and $\gcd(g,x)=1$. From $(p+1)(q+1)=\sigma(f)(r+1)$ we obtain $q+1=gy$ and $r+1=xy$ for an integer $y$. With $A(a)=2-c/b$, the second condition is

$$Exy-bhx-bgy=b(f-1),\qquad E=bf-bgh+cgh.$$

If $E\ne0$, completion gives

$$(Ex-bg)(Ey-bh)=b^2gh+bE(f-1).$$

Thus fixing $a,f$ and a factorization $\sigma(f)=hg$ reduces the nondegenerate case to factor pairs, followed by all the original checks, including $\gcd(g,x)=1$. If $E=0$, one must inspect the preceding linear equation; dividing by $E$ is invalid. Here $b,g,h,x,y$ are positive and $f\ge1$, so its left side is negative and its right side nonnegative: there is no solution. This also explains the excluded $a=4,f=3$ case reported on p. 44.

Problem 4: different residual factors on both sides

For $agpq,ahr$, assume $g,h,p,q,r$ are primes, distinct within each residual product, and that $a$ is coprime to both products. The common-factor criterion becomes

$$(g+1)(p+1)(q+1)=(h+1)(r+1),$$ $$A(a)(g+1)(p+1)(q+1)=gpq+hr.$$

Put $g+1=k\mu$, $h+1=k\nu$ with $\gcd(\mu,\nu)=1$. The first equation says $\mu(p+1)(q+1)=\nu(r+1)$; after finding $r$, the second tests the required abundance. This is the same residual-sum matching principle with more adjustable factors. It does not make the additional prime tests disappear.

Dickson reports successful choices, including $a=10,k=8,\mu=3,\nu=1$, giving $g=23,h=7$. Put $x=p+1$, $y=q+1$, so $r=3xy-1$. The second equation becomes $4xy-115x-115y+80=0$, or

$$(4x-115)(4y-115)=12905.$$

The factor pair $(5,2581)$ gives $x=30$, $y=674$ and the primes $p=29$, $q=673$, $r=60659$. Thus

$$M=10\cdot23\cdot29\cdot673=4488910,$$ $$N=10\cdot7\cdot60659=4246130.$$

Both divisor sums are $18\cdot24\cdot30\cdot674=18\cdot8\cdot60660=8735040=M+N$. This verifies a worked instance; it does not reproduce every case of Euler's fourth problem.

Problem 5: solve for the common factor too

Seek $zap,zbq$, with $a,b$ fixed, $p,q$ prime, $\gcd(a,p)=\gcd(b,q)=1$ and $\gcd(z,abpq)=1$. We state these separations explicitly. Reduce $\sigma(a)/\sigma(b)=m/n$. Matching the residual divisor sums forces $p+1=nx$, $q+1=mx$. Then

$$\frac z{\sigma(z)}=\frac{nx\sigma(a)}{(na+mb)x-a-b}.$$

Reduce this positive fraction to $r/s$. If such a $z$ exists, $z=kr$ and $\sigma(z)=ks$ for an integer $k$. Since $r\mid z$, the divisibility monotonicity of $A$ gives

$$s\ge\sigma(r).$$

This is Euler's useful rejection test. It is necessary, not sufficient: surviving it does not produce a number with the prescribed ratio, much less guarantee its coprimality with $abpq$. For example, for $a=5,b=1,x=2$, both proposed primes $p=1,q=11$ already fail because 1 is not prime. For $x=4$, $p=3,q=23$ are prime but $z/\sigma(z)=24/38=12/19$ fails the test since $\sigma(12)=28>19$. The local arithmetic can reject a plausible prime pair before searching for $z$.

The limit of a prescribed pattern

Paganini's pair has

$$1184=2^5\cdot37,\qquad1210=2\cdot5\cdot11^2,$$ $$\sigma(1184)=63\cdot38=2394=3\cdot6\cdot133=\sigma(1210).$$

Its sum is also 2394. The greatest common divisor is 2, but removing it leaves 592 and 605; 592 still has a factor 2. No nontrivial common factor is coprime to both residual numbers. Consequently this pair lies outside the separated-common-factor setting underlying the first four problems. Taking $a=1$ does not repair the first ansatz: neither number is prime, as its $ar$ member would require.

A construction can therefore be complete within its assumptions and still miss a smaller example of the unrestricted problem. Dickson's record of omitted, false and newly found pairs makes this limitation mathematically useful.