On $\phi$-amicable pairs

Authors:
Graeme L. Cohen and Herman J. J. te Riele

Journal:
Math. Comp. **67** (1998), 399-411

MSC (1991):
Primary 11A25, 11Y70

DOI:
https://doi.org/10.1090/S0025-5718-98-00933-8

MathSciNet review:
1458219

Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: Let $\phi (n)$ denote Euler’s totient function, i.e., the number of positive integers $<n$ and prime to $n$. We study pairs of positive integers $(a_{0},a_{1})$ with $a_{0}\le a_{1}$ such that $\phi (a_{0})=\phi (a_{1})=(a_{0}+a_{1})/k$ for some integer $k\ge 1$. We call these numbers $\phi$–*amicable pairs with multiplier* $k$, analogously to Carmichael’s multiply amicable pairs for the $\sigma$–function (which sums all the divisors of $n$). We have computed all the $\phi$–amicable pairs with larger member $\le 10^{9}$ and found $812$ pairs for which the greatest common divisor is squarefree. With any such pair infinitely many other $\phi$–amicable pairs can be associated. Among these $812$ pairs there are $499$ so-called primitive $\phi$–amicable pairs. We present a table of the $58$ primitive $\phi$–amicable pairs for which the larger member does not exceed $10^{6}$. Next, $\phi$–amicable pairs with a given prime structure are studied. It is proved that a relatively prime $\phi$–amicable pair has at least twelve distinct prime factors and that, with the exception of the pair $(4,6)$, if one member of a $\phi$–amicable pair has two distinct prime factors, then the other has at least four distinct prime factors. Finally, analogies with construction methods for the classical amicable numbers are shown; application of these methods yields another 79 primitive $\phi$–amicable pairs with larger member $>10^{9}$, the largest pair consisting of two 46-digit numbers.

- Walter Borho,
*Eine Schranke für befreundete Zahlen mit gegebener Teileranzahl*, Math. Nachr.**63**(1974), 297–301 (German). MR**364071**, DOI https://doi.org/10.1002/mana.3210630125 - W. Borho,
*Some large primes and amicable numbers*, Math. Comp.**36**(1981), no. 153, 303–304. MR**595068**, DOI https://doi.org/10.1090/S0025-5718-1981-0595068-2 - Sonja Brentjes and Jan P. Hogendijk,
*Notes on Thābit ibn Qurra and his rule for amicable numbers*, Historia Math.**16**(1989), no. 4, 373–378 (English, with French and German summaries). MR**1040183**, DOI https://doi.org/10.1016/0315-0860%2889%2990084-0 - R. D. Carmichael,
*Review of*, Amer. Math. Monthly*History of the Theory of Numbers***26**(1919), 396–403. - G. L. Cohen and H. J. J. te Riele,
*On $\phi$–amicable pairs (̊with appendix)̊*, Research Report R95-9 (December 1995), School of Mathematical Sciences, University of Technology, Sydney, and CWI-Report NM-R9524 (November 1995), CWI Amsterdam, ftp://ftp.cwi.nl/pub/CWIreports/NW/NM-R9524.ps.Z. - Richard K. Guy,
*Unsolved problems in number theory*, 2nd ed., Problem Books in Mathematics, Springer-Verlag, New York, 1994. Unsolved Problems in Intuitive Mathematics, I. MR**1299330** - Miriam Hausman,
*The solution of a special arithmetic equation*, Canad. Math. Bull.**25**(1982), no. 1, 114–117. MR**657659**, DOI https://doi.org/10.4153/CMB-1982-015-x - T. E. Mason,
*On amicable numbers and their generalizations*, Amer. Math. Monthly**28**(1921), 195–200. - H. Jager (ed.),
*Number theory, Noordwijkerhout 1983*, Lecture Notes in Mathematics, vol. 1068, Springer-Verlag, Berlin, 1984. MR**756078** - H. J. J. te Riele,
*Computation of all the amicable pairs below $10^{10}$*, Math. Comp.**47**(1986), no. 175, 361–368, S9–S40. With a supplement. MR**842142**, DOI https://doi.org/10.1090/S0025-5718-1986-0842142-3

Retrieve articles in *Mathematics of Computation*
with MSC (1991):
11A25,
11Y70

Retrieve articles in all journals with MSC (1991): 11A25, 11Y70

Additional Information

**Graeme L. Cohen**

Affiliation:
School of Mathematical Sciences, University of Technology, Sydney, PO Box 123, Broadway, NSW 2007, Australia

Email:
glc@maths.uts.edu.au

**Herman J. J. te Riele**

Affiliation:
CWI, Department of Modeling, Analysis and Simulation, Kruislaan 413, 1098 SJ Amsterdam, The Netherlands

Email:
herman@cwi.nl

Keywords:
Euler’s totient function,
$\phi$–amicable pairs

Received by editor(s):
November 28, 1995

Received by editor(s) in revised form:
May 10, 1996

Article copyright:
© Copyright 1998
American Mathematical Society