Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



On $\boldsymbol \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
MathSciNet review: 1458219
Full-text PDF

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.

References [Enhancements On Off] (What's this?)

  • 1. W. Borho, Eine Schranke für befreundete Zahlen mit gegebener Teileranzahl, Math. Nachr. 63 (1974), 297-301. MR 51:326
  • 2. W. Borho, Some large primes and amicable numbers, Math. Comp. 36 (1981), 303-304. MR 82d:10021
  • 3. Sonja Brentjes and Jan P. Hogendijk, Notes on Th\={a}bit ibn Qurra and his rule for amicable numbers, Historia Math. 16 (1989), 373-378. MR 91m:01004
  • 4. R. D. Carmichael, Review of History of the Theory of Numbers, Amer. Math. Monthly 26 (1919), 396-403.
  • 5. 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, .
  • 6. Richard K. Guy, Unsolved Problems in Number Theory, Springer-Verlag, New York, etc., 1994, second edition. MR 96e:11002
  • 7. Miriam Hausman, The solution of a special arithmetic equation, Canad. Math. Bull. 25 (1982), 114-117. MR 83i:10019
  • 8. T. E. Mason, On amicable numbers and their generalizations, Amer. Math. Monthly 28 (1921), 195-200.
  • 9. H. J. J. te Riele, New very large amicable pairs, Number Theory Noordwijkerhout 1983 (H. Jager, ed.), Springer-Verlag, 1984, pp. 210-215. MR 85i:11001
  • 10. H. J. J. te Riele, Computation of all amicable pairs below $10^{10}$, Math. Comp. 47 (1986), 361-368, S9-S40. MR 87i:11014

Similar Articles

Retrieve articles in Mathematics of Computation of the American Mathematical Society 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

Herman J. J. te Riele
Affiliation: CWI, Department of Modeling, Analysis and Simulation, Kruislaan 413, 1098 SJ Amsterdam, The Netherlands

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

American Mathematical Society