On -amicable pairs

• Published in: Mathematics of computation 1998-01, Vol.67 (221), p.399-411
• Main Authors: Cohen, Graeme, te Riele, Herman
• Format: Article
• Language: English
• ISSN: 0025-5718; 1088-6842
• DOI: 10.1090/S0025-5718-98-00933-8

Let ϕ ( n ) \phi (n) denote Euler’s totient function, i.e., the number of positive integers  > n >n and prime to n n . We study pairs of positive integers ( a 0 , a 1 ) (a_{0},a_{1}) with a 0 ≤ a 1 a_{0}\le a_{1} such that ϕ ( a 0 ) = ϕ ( a 1 ) = ( a 0 + a 1 ) / k \phi (a_{0})=\phi (a_{1})=(a_{0}+a_{1})/k for some integer k ≥ 1 k\ge 1 . We call these numbers ϕ \phi – amicable pairs with multiplier k k , analogously to Carmichael’s multiply amicable pairs for the σ \sigma –function (which sums all the divisors of n n ). We have computed all the ϕ \phi –amicable pairs with larger member ≤ 10 9 \le 10^{9} and found 812 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 812 pairs there are 499 499 so-called primitive ϕ \phi –amicable pairs. We present a table of the 58 58 primitive ϕ \phi –amicable pairs for which the larger member does not exceed 10 6 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 ) (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 >10^{9} , the largest pair consisting of two 46-digit numbers.